Simple Java recursive solution


  • 2

    If the root is well within the range, then just delegating the problem to left and right subtrees.
    if the root is out of the range and less than L, then the entire left subtree can be discarded including the root.
    if the root is out of the range and greater than R, then the entire right subtree can be discarded including the root.

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

  • 1
    S

    This pre-order recursion solution is better than the post-order one.
    In post-order trimming, we have to visit every node. With pre-order, if(root.val < L) and if(root.val > R), we only need to process one subtree instead of two.
    C++ version of the pre-order solution:

    class Solution {
    
    public:
        TreeNode* trimBST(TreeNode* root, int L, int R) {
            if (root == nullptr)
                return nullptr;
            if (root->val >= L && root->val <= R){
                root->left = trimBST(root->left, L, R);
                root->right = trimBST(root->right, L, R);
                return root;
            }
            if (root->val < L)
                return trimBST(root->right, L, R);
            if (root->val > R)
                return trimBST(root->left, L, R);
            
        }
    };

  • 0

    @shuhua thanks .


Log in to reply
 

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