修剪二叉搜索树
难度:
标签:
题目描述
给你二叉搜索树的根节点 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]
提示：
- 树中节点数在范围
[1, 104]内 0 <= Node.val <= 104- 树中每个节点的值都是 唯一 的
- 题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 104
代码结果
运行时间: 60 ms, 内存: 19.2 MB
/*
题目思路：
由于Java Stream API不适合操作树结构，因此这里提供传统Java实现方法。
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return null;
if (root.val < low) return trimBST(root.right, low, high);
if (root.val > high) return trimBST(root.left, low, high);
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}解释
方法:
这个题解使用递归的方式对二叉搜索树进行修剪。具体思路如下：
1. 如果当前节点为空，直接返回。
2. 如果当前节点的值小于下限 low，说明该节点及其左子树都应该被剪掉，返回对右子树修剪的结果。
3. 如果当前节点的值大于上限 high，说明该节点及其右子树都应该被剪掉，返回对左子树修剪的结果。
4. 如果当前节点的值在 [low, high] 范围内，则递归地对左子树和右子树进行修剪，并返回修剪后的当前节点。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在递归过程中，如果当前节点的值小于下限`low`，为什么选择返回修剪后的右子树的结果而不考虑左子树？
▷🦆
对于值大于上限`high`的节点，仅返回左子树的修剪结果是否意味着右子树的所有节点都不在范围内？
▷🦆
递归修剪左子树和右子树后为何可以直接将结果赋值给`root.left`和`root.right`？这种操作是否会影响树的结构或造成节点丢失？
▷🦆
题解中对于节点值在[low, high]范围内的处理逻辑是否保证了修剪后的树仍然满足二叉搜索树的所有性质？
▷