669. Trim a Binary Search Tree
Time: O(n), Space: O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) {
return root;
}
// If the value of this node is less than L, return the root of the trimmed right sub tree
if (root.val < L) {
return trimBST(root.right, L, R);
}
// If the value of this node is greater than R, return the root of the trimmed left sub tree
if (root.val > R) {
return trimBST(root.left, L, R);
}
// If the value of this node does not need to be deleted, we need to pass this recursive call downwards to both sides
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
// All the processing of the subtrees done, now return this node
return root;
}
}
Referred to this post.