LeetCode 669. 修剪二叉搜索树

思路

• 遍历所有节点，如果当前节点不在所给区间里，删除该点；否则
• 如果该点要被删除，将其左右子树其中之一提上来即可
  • 根节点位于左右子树取值区间的中间，如果该点要被删除，那么一定存在不满足要求的子树，不可能两棵子树同时保留

代码

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;
    }
};