修剪二叉搜索树

给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。

示例 1:

输入:
1
/
0 2

L = 1
R = 2

输出:
1

2
示例 2:

输入:
3
/
0 4

2
/
1

L = 1
R = 3

输出:
3
/
2
/
1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/trim-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

递归
题目要求返回BST被修剪后的根结点,那么我们从根结点开始修剪。
如果根结点太小,根结点的左子树的所有结点只会更小,说明根结点及其左子树都应该剪掉,因此直接返回右子树的修剪结果。
如果根结点太大,根结点的右子树的所有结点只会更大,说明根结点及其右子树都应该剪掉,因此直接返回左子树的修剪结果。
如果根结点没问题,则递归地修剪左子结点和右子结点。
如果结点为空,说明无需修剪,直接返回空即可。
左右子结点都修剪完后,返回自身。

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

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。