669. 修剪二叉搜索树
LeetCode题目要求
给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。
![图](/i/l/?n=23&i=blog/458364/202301/458364-20230126211458436-1606376663.png)
示例
输入:root = [1,0,2], low = 1, high = 2
输出:[1,null,2]
解题思路
根据范围修剪树,且是二叉搜索树,那么在修剪后需要保持二叉搜索树。
所以按照范围约束,
- 如果节点值 < low , 那么它的左子树就都不要考虑了,需要遍历它的右子树,可能是在范围内;
- 如果节点值 > high, 那么右子树不需要扣了,而要处理左子树,这里大家不要认为 low 或 high 一定是 节点范围内的值;
- 如果再 low 到 high 范围内,那么就直接取节点好了
上代码
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
// 确定终止条件
if (root == null) {
return null;
}
int val = root.val;
// 如果 节点值 小于 low,左节点肯定小于 当前节点值,不需要考虑;只看 右节点,如果在范围内就 按二叉搜索树构造
if (val < low) {
return trimBST(root.right, low, high);
}
// 如果 节点值 大于 high,需要遍历左节点,因为左节点可能是在范围内的
if (val > high) {
return trimBST(root.left, low, high);
}
// 在 low -> high 范围内的直接取节点
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
重难点
二叉树的特性,范围内修剪,主要的不单单考虑节点是在范围内就可以,还要主要它们的左右子树
附:学习资料链接
标签:修剪,669,23,Day,high,low,二叉,root,节点 From: https://www.cnblogs.com/blacksonny/p/17068253.html