Java recursion with explanation


  • 0

    If the root value < L, then all its left subtree's values < L
    then we only need to consider and return its right subtree result;

    if the root value > R, then all its right subtree's values > R
    then we only need to consider and return its left subtree result;

    if the L <= root value <= R, we will return the root;
    and all its left children need to <= root.value
    and all its right children need to >= root.value

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

Log in to reply
 

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