Solution by awice


  • 0

    Approach #1: Recursion [Accepted]

    Intuition

    Let trim(node) be the desired answer for the subtree at that node. We can construct the answer recursively.

    Algorithm

    When node.val > R, we know the trimmed binary tree must occur to the left of the node. Similarly, when node.val < L, the trimmed binary tree occurs to the right of the node. Otherwise, we will trim both sides of the tree.

    Java

    class Solution {
        public TreeNode trimBST(TreeNode root, int L, int R) {
            if (root == null) return root;
            if (root.val > R) return trimBST(root.left, L, R);
            if (root.val < L) return trimBST(root.right, L, R);
    
            root.left = trimBST(root.left, L, R);
            root.right = trimBST(root.right, L, R);
            return root;
        }
    }
    

    Python

    class Solution(object):
        def trimBST(self, root, L, R):
            def trim(node):
                if not node:
                    return None
                elif node.val > R:
                    return trim(node.left)
                elif node.val < L:
                    return trim(node.right)
                else:
                    node.left = trim(node.left)
                    node.right = trim(node.right)
                    return node
    
            return trim(root)
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the total number of nodes in the given tree. We visit each node at most once.

    • Space Complexity: $$O(N)$$. Even though we don't explicitly use any additional memory, the call stack of our recursion could be as large as the number of nodes in the worst case.


Log in to reply
 

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