Leetcode 669. 修剪二叉搜索树
给你二叉搜索树的根节点 root
,同时给定最小边界 low
和最大边界 high
。通过修剪二叉搜索树,使得所有节点的值在 [low, high]
中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。
示例 1:
输入:root = [1,0,2], low = 1, high = 2 输出:[1,null,2]
示例 2:
输入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输出:[3,2,null,1]
解题思路:
具体的解题思路如下:
- 首先判断根节点
root
是否为空。如果为空,表示当前子树为空树,直接返回空。 - 比较根节点的值
root.val
与给定的范围[low, high]
。- 如果
root.val
小于最小值low
,说明根节点及其左子树的所有节点都小于low
,这意味着它们都不符合要求。由于二叉搜索树的性质,右子树中的节点值肯定大于root.val
,所以我们只需要在右子树中寻找符合要求的节点。因此,递归调用trimBST(root.right, low, high)
,并返回修剪后的右子树。 - 如果
root.val
大于最大值high
,说明根节点及其右子树的所有节点都大于high
,这意味着它们都不符合要求。由于二叉搜索树的性质,左子树中的节点值肯定小于root.val
,所以我们只需要在左子树中寻找符合要求的节点。因此,递归调用trimBST(root.left, low, high)
,并返回修剪后的左子树。 - 如果
root.val
在范围[low, high]
内,说明根节点的值符合要求。但是左子树和右子树中的节点值可能不符合要求,所以需要分别修剪左子树和右子树。- 递归调用
trimBST(root.left, low, high)
,将返回的修剪后的左子树连接到root
的左节点上。 - 递归调用
trimBST(root.right, low, high)
,将返回的修剪后的右子树连接到root
的右节点上。
- 递归调用
- 最后返回修剪后的根节点
root
。
- 如果
代码实现:
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root == null){ // 如果根节点为空,直接返回空
return root;
}
// 如果根节点的值小于最小值 low,则说明根节点及其左子树都不符合要求,递归地在右子树中寻找符合要求的节点
if(root.val < low){
return trimBST(root.right, low, high);
// 如果根节点的值大于最大值 high,则说明根节点及其右子树都不符合要求,递归地在左子树中寻找符合要求的节点
}else if(root.val > high){
return trimBST(root.left, low, high);
}
// 如果根节点的值在 [low, high] 范围内,则需要修剪左右子树
// 修剪左子树,递归调用 trimBST 方法
root.left = trimBST(root.left, low, high);
// 修剪右子树,递归调用 trimBST 方法
root.right = trimBST(root.right, low, high);
// 返回修剪后的根节点
return root;
}
}
代码跟踪:
当输入为 root = [3,0,4,null,2,null,null,1]
,low = 1
,high = 3
时,我们来演示代码的执行过程和修剪后的结果。
首先,我们将输入的二叉树可视化:
3
/ \
0 4
\
2
/
1
根据代码的逻辑,我们从根节点开始进行修剪操作:
- 根节点的值为 3,它在范围 [1, 3] 内,所以我们需要修剪它的左子树和右子树。
- 考虑左子树,根节点的左子节点是 0。由于 0 < 1,不在范围内,所以我们需要在0的右子树中寻找符合要求的节点。
- 在右子树中,根节点的左子节点是 2,它的值在范围 [1, 3] 内,符合要求。我们需要修剪它的左子树和右子树。
- 考虑左子树,根节点的左子节点是 1,它的值在范围 [1, 3] 内,符合要求。它没有左子树和右子树,不需要进一步修剪。
- 考虑右子树,根节点的右子节点为空,不需要修剪。
- 最后回到3的右子树中,根节点的右子节点是 4。由于 4 > 3,不在范围内,所以我们需要在4的左子树中寻找符合要求的节点。4的左子树为空,所以返回null
- 修剪完左子树和右子树后,将修剪后的0的右子树连接到根节点3的左节点上。4的左子树连接到根节点3的右节点上,即为null。
修剪后的二叉树如下:
3
/
2
/
1
输出为 [3,2,1]
,符合要求的节点值在范围 [1, 3] 内。
评论区