思路
- 遍历所有节点，如果当前节点不在所给区间里，删除该点；否则
- 如果该点要被删除，将其左右子树其中之一提上来即可
- 根节点位于左右子树取值区间的中间，如果该点要被删除，那么一定存在不满足要求的子树，不可能两棵子树同时保留
代码
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int l, int r) {
if(!root) return NULL;
if(root->val<l)//根节点小于区间左端点，删除一定不满足要求的左子树
return trimBST(root->right,l,r);
if(root->val>r)//根节点大于区间右端点，删除一定不满足要求的右子树
return trimBST(root->left,l,r);
//如果当前根节点满足要求，修剪其左右子树
root->left=trimBST(root->left,l,r);
root->right=trimBST(root->right,l,r);
return root;
}
};