Python Iterative solution using Pre-order traversal


  • 0
    5

    This is like using the pre-order traversal iterative approach. Whenever we get a current node, it is already within the boundary (otherwise it is removed in a previous step). Then adjust the left & right children until they are within the range (or None). Push the right child if it is not None for future adjustment.

    A dummy node with infinite value is useful to avoid potential bugs.

    class Solution(object):
        def trimBST(self, root, L, R):
            """
            :type root: TreeNode
            :type L: int
            :type R: int
            :rtype: TreeNode
            """
            def out_of_bound(node):
                return not L <= node.val <= R
            
            dummy = TreeNode(float('inf'))
            dummy.left = root
            stack = []
            root = dummy
            
            while root or stack: # Same loop guards as pre-order traversal
                if not root:
                    root = stack.pop()
                else:
                    while root.left and out_of_bound(root.left): # Keep adjusting the left child
                        root.left = root.left.right if root.left.val < L else root.left.left
                    while root.right and out_of_bound(root.right): # Keep adjusting the right child
                        root.right = root.right.right if root.right.val < L else root.right.left
                    if root.right:
                        # Check the right subtree later
                        stack.append(root.right)
                    root = root.left
            return dummy.left
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.