LC669. 修剪二叉搜索树

迭代

def trimBST(self, root, low, high):
        """ :type root: TreeNode :type low: int :type high: int :rtype: TreeNode """
        if not root:
            return 
        while root and (root.val < low or root.val > high):  #找到合法的root
            if root.val < low:
                root = root.right
            elif root.val > high:
                root = root.left
        cur = root 
        while cur:
            while cur.left and cur.left.val < low:  #找左边不合格的
                cur.left = cur.left.right           #找到之后左子树所有的都可以丢掉，并且把不合格节点的右子树连接到cur上 
            cur = cur.left                          #接着找（根据二叉树的特性没找到就一直往左找）
        cur = root
        while cur:
            while cur.right and cur.right.val > high: #找右边不合格的
                cur.right = cur.right.left            #找到后右子树的所有都可以丢掉，并且把不合格节点的左子树连接到cur上
            cur = cur.right                           #接着找（根据二叉树的特性没找到就一直往右找）
        return root

递归

def trimBST(self, root, low, high):  #从根节点开始修剪
        """ :type root: TreeNode :type low: int :type high: int :rtype: TreeNode """
        if not root:
            return 
        if root.val < low: 
            return self.trimBST(root.right,low,high)  #这里是进行修剪，并且最后返回修剪之后的结果(是先运行递归的语句，最后返回到当前语句时，才会执行return)
            # 等价于
            # left = self.trimBST(root.right,low,high) #先执行递归，返回到这一句时才会执行下面的那句
            # return left
        elif root.val > high: 
            return self.trimBST(root.left,low,high)
        root.left = self.trimBST(root.left,low,high)   #如果根节点没问题，则递归地修剪左子结点和右子结点
        root.right = self.trimBST(root.right,low,high)
        return root

递归，相当于自底向上的构建，先把所有的修剪完毕，之后return root时慢慢连接，最后把修剪好的左右子树连接上。

def trimBST(self, root, low, high):
        """ :type root: TreeNode :type low: int :type high: int :rtype: TreeNode """
        if not root:
            return 
        if root.val >= low:  #正常就修剪左子节点和右子节点
            root.left = self.trimBST(root.left,low,high) 
        else:   #如果根节点太小，且他的左子树都小于它所以直接返回右子树的修剪结果就行
            return self.trimBST(root.right,low,high)
        if root.val <= high:
            root.right = self.trimBST(root.right,low,high)
        else:  #如果根节点太大，且他的右子树都大于它所以直接返回左子树的修剪结果就行
            return self.trimBST(root.left,low,high)
        return root