Python Easy to Understand

  • 1

    This problem can be solved recursively. When the node's value is not within the range, we have to find a replacement, which is either the trimmed left child or right child or neither.

    - Yangshun

    class Solution(object):
        def trimBST(self, root, L, R):
            :type root: TreeNode
            :type L: int
            :type R: int
            :rtype: TreeNode
            # Time: O(n)
            # Space: O(lgn)
            def trim(node):
                if not node:
                    return None
                node.left, node.right = trim(node.left), trim(node.right)
                # Node's value is not within range, 
                # select one or none of its children as replacement.
                if not (L <= node.val <= R):
                    node = node.left if node.left else node.right
                return node
            return trim(root)

Log in to reply

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