669. 修剪二叉搜索树 : 常规树的遍历与二叉树性质
题目描述
这是 LeetCode 上的 669. 修剪二叉搜索树 ,难度为 中等 。
Tag : 「BST」、「二叉树」、「递归」、「迭代」
给你二叉搜索树的根节点 root
,同时给定最小边界 low
和最大边界 high
。通过修剪二叉搜索树,使得所有节点的值在 $[low, high]$ 中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。
示例 1:
![](http://mdimg.wxwenku.com/getimg/356ed03bdc643f9448b3f6485edc229b848611cf05e47bc2820ecb6b5c1bb07f5c86deee1752ddfe519cc8118019c034.jpg)
输入:root = [1,0,2], low = 1, high = 2 输出:[1,null,2]
示例 2:
![](http://mdimg.wxwenku.com/getimg/356ed03bdc643f9448b3f6485edc229b8fe8117c4eb19a78441abac80df553f8e657389be3f5ca9095486fa21e23ae08.jpg)
输入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输出:[3,2,null,1]
提示:
- 树中节点数在范围 $[1, 10^4]$ 内
- $0 <= Node.val <= 10^4$
- 树中每个节点的值都是 唯一 的
- 题目数据保证输入是一棵有效的二叉搜索树
- $0 <= low <= high <= 10^4$
递归
由于被修剪的是二叉搜索树,因此修剪过程必然能够顺利进行。
容易想到使用原函数作为递归函数:
- 若
root.val
小于边界值low
,则root
的左子树必然均小于边界值,我们递归处理root.right
即可; - 若
root.val
大于边界值high
,则root
的右子树必然均大于边界值,我们递归处理root.left
即可; - 若
root.val
符合要求,则root
可被保留,递归处理其左右节点并重新赋值即可。
Java 代码:
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); else 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; } }
TypeScript 代码:
function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null { if (root == null) return null if (root.val < low) return trimBST(root.right, low, high) else 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 };
- 时间复杂度:$O(n)$
- 空间复杂度:忽略递归带来的额外空间开销,复杂度为 $O(1)$
迭代
自然能够使用「迭代」进行求解:起始先从给定的 root
进行出发,找到第一个满足值符合 $[low, high]$ 范围的节点,该节点为最后要返回的根节点 ans
。
随后考虑如何修剪 ans
的左右节点:当根节点符合 $[low, high]$ 要求时,修剪左右节点过程中仅需考虑一边的边界值即可。即对于 ans.left
只需考虑将值小于 low
的节点去掉(因为二叉搜索树的特性, ans
满足不大于 high
要求,则其左节点必然满足);同理 ans.right
只需要考虑将大于 high
的节点去掉即可。
Java 代码:
class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { while (root != null && (root.val < low || root.val > high)) root = root.val < low ? root.right : root.left; TreeNode ans = root; while (root != null) { while (root.left != null && root.left.val < low) root.left = root.left.right; root = root.left; } root = ans; while (root != null) { while (root.right != null && root.right.val > high) root.right = root.right.left; root = root.right; } return ans; } }
TypeScript 代码:
function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null { while (root != null && (root.val < low || root.val > high)) root = root.val < low ? root.right : root.left const ans = root while (root != null) { while (root.left != null && root.left.val < low) root.left = root.left.right root = root.left } root = ans while (root != null) { while (root.right != null && root.right.val > high) root.right = root.right.left root = root.right } return ans };
- 时间复杂度:$O(n)$
- 空间复杂度:$O(1)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.669
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库: http://github.com/SharingSou... 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地 :tada::tada:
本文由mdnice多平台发布
- 天翼云全场景业务无缝替换至国产原生操作系统CTyunOS!
- 以羊了个羊为例,浅谈小程序抓包与响应报文修改
- 这几种常见的 JVM 调优场景,你知道吗?
- 如此狂妄,自称高性能队列的Disruptor有啥来头?
- 为什么要学习GoF设计模式?
- 827. 最大人工岛 : 简单「并查集 枚举」运用题
- 手把手教你如何使用 Timestream 实现物联网时序数据存储和分析
- 850. 矩形面积 II : 扫描线模板题
- Java 并发编程解析 | 基于JDK源码解析Java领域中的并发锁,我们可以从中学习到什么内容?
- 【手把手】光说不练假把式,这篇全链路压测实践探索
- 大厂钟爱的全链路压测有什么意义?四种压测方案详细对比分析
- 写个续集,填坑来了!关于“Thread.sleep(0)这一行‘看似无用’的代码”里面留下的坑。
- 857. 雇佣 K 名工人的最低成本 : 枚举 优先队列(堆)运用题
- Vue3 实现一个自定义toast(小弹窗)
- 669. 修剪二叉搜索树 : 常规树的遍历与二叉树性质
- 读完 RocketMQ 源码,我学会了如何优雅的创建线程
- 性能调优——小小的log大大的坑
- 1582. 二进制矩阵中的特殊位置 : 简单模拟题
- elementui源码学习之仿写一个el-switch
- 646. 最长数对链 : 常规贪心 DP 运用题