Trim a Binary Search Tree
给一个BST, 然后给一个L和R两个整数, 给BST剪枝(trim), 问剪枝后的树. 这个题很有意思, 首先要理解剪枝这个操作, 仅仅是针对当前node的. 而对于node的子树,需要重新判断, 那么这个题就是一个子问题划分的题, 我们要通过递归不断把问题分解. 通过观察example, 我们可以看出, node.val如果大于R, 那么node的右边的子树都大于R, 那么都应该剪掉, 所以返回node的左边, 并且继续子问题探索. 同理对node.val小于R的情况. 如果node.val在L和R之间, 那么我们只需要继续分开讨论左边和右边子问题即可.
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);
else {
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
}
}