深度优先遍历 DFS
解题思路
删除 BST 中不在 [low, high] 的所有节点；
如果一个节点的值没有落在 [low, high] 范围内，有两种情况：
root.val < low这种情况下 root 的左子树一定都小于 low 则都要删除，需要递归扫描返回 右子树 符合在 [low, high] 的节点；root.val > high这种情况下 root 的右子树一定都大于 high 则都要删除，需要递归扫描返回 左子树 符合 [low, high] 的节点；
图解
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树的结点数目； -
空间复杂度：
O(n)，递归栈最坏情况下需要O(n)的空间；
实现代码
var trimBST = function (root, low, high) {
if (root === null) return root;
// 1. 删除节点
if (root.val < low) {
// 当前节点的值 < low，则 当前节点的左子树一定都 < low 则都要删除，需要递归扫描返回右子树符合 [low, high] 的节点
return trimBST(root.right, low, high);
} else if (root.val > high) {
// 当前节点的值 > low，则 当前节点的右子树一定都 > high 则都要删除，需要递归扫描返回左子树符合 [low, high] 的节点
return trimBST(root.left, low, high);
}
// 2. 递归处理左右子树
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
};
广度优先遍历 BFS
解题思路
首先要找到根节点，从树的根节点出发，向下寻找第一个满足在 [low, high] 范围的节点 root；
此时根节点符合 [low, high] 要求，然后根据 root 修剪掉不满足的左右子节点，由于是二叉搜索树，则修剪左右节点过程中仅需考虑一边的边界值即可：
- 对于 root.left 只需考虑将值小于 low 的节点去掉；
- 同理 root.right 只需要考虑将大于 high 的节点去掉即可；
图解
这里对 对于 root.left 只需考虑将值小于 low 的节点去掉 进行演示
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树的结点数目； -
空间复杂度：
O(1)；
实现代码
var trimBST = function (root, low, high) {
if (root === null) return null;
// 1. 寻找第一个满足在 [low, high] 范围的节点 root，root 就是最后返回的根节点
while (root && (root.val < low || root.val > high)) {
root = root.val < low ? root.right : root.left;
}
// 2. 对于 root.left 只需考虑将值小于 low 的节点去掉；
let cur = root;
while (cur) {
while (cur.left && cur.left.val < low) {
cur.left = cur.left.right;
}
cur = cur.left;
}
// 3. 同理 root.right 只需要考虑将大于 high 的节点去掉即可；
cur = root;
while (cur) {
while (cur.right && cur.right.val > high) {
cur.right = cur.right.left;
}
cur = cur.right;
}
return root;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 167. 两数之和 II - 输入有序数组
上一篇
评论
