Lc669. Prune binary search tree

iteration

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):  # Find the legal 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:  # Find the unqualified one on the left 
                cur.left = cur.left.right           # After finding it, all the left subtree can be discarded , And connect the right subtree of the unqualified node to cur On  
            cur = cur.left                          # Keep looking （ According to the characteristics of binary tree, if you don't find it, keep looking to the left ）
        cur = root
        while cur:
            while cur.right and cur.right.val > high: # Find the unqualified one on the right 
                cur.right = cur.right.left            # After finding the right subtree, all can be discarded , And connect the left subtree of the unqualified node to cur On 
            cur = cur.right                           # Keep looking （ According to the characteristics of binary tree, if you don't find it, keep looking to the right ）
        return root

recursive

def trimBST(self, root, low, high):  # Trim from the root node 
        """ :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)  # Here is for pruning , And finally return the pruned result ( Is to run recursive statements first , Finally, when you return to the current statement , Will execute return)
            #  Equivalent to 
            # left = self.trimBST(root.right,low,high) # First perform recursion , The following sentence will be executed only when you return to this sentence 
            # return left
        elif root.val > high: 
            return self.trimBST(root.left,low,high)
        root.left = self.trimBST(root.left,low,high)   # If the root node is ok , Then recursively prune the left and right child nodes 
        root.right = self.trimBST(root.right,low,high)
        return root

recursive , Equivalent to bottom-up construction , First finish all the pruning , after return root Connect slowly , Finally, connect the pruned left and right subtrees .

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:  # Prune the left and right child nodes normally 
            root.left = self.trimBST(root.left,low,high) 
        else:   # If the root node is too small , And its left subtree is smaller than it, so just return to the pruning result of the right subtree 
            return self.trimBST(root.right,low,high)
        if root.val <= high:
            root.right = self.trimBST(root.right,low,high)
        else:  # If the root node is too large , And its right subtree is larger than it, so just return to the pruning result of the left subtree 
            return self.trimBST(root.left,low,high)
        return root