二叉搜索树的区间修剪算法

在这里插入图片描述

核心思想

利用BST的关键特性：左子树所有节点的值都小于根节点，右子树所有节点的值都大于根节点。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public static TreeNode trimBST(TreeNode cur, int low, int high){
    // 递归终止条件：遇到空节点直接返回
    if(cur == null){
        return null;
    }
    
    // 情况1：当前节点太小，答案一定在右子树
    if(cur.val < low){
        return trimBST(cur.right, low, high);
    }
    
    // 情况2：当前节点太大，答案一定在左子树
    if(cur.val > high){
        return trimBST(cur.left, low, high);
    }
    
    // 情况3：当前节点在范围内，保留它，并递归修剪左右子树
    cur.left = trimBST(cur.left, low, high);
    cur.right = trimBST(cur.right, low, high);
    
    return cur;
}

如果觉得有帮助，欢迎点赞、关注、转发~