Leetcode No.99 恢复二叉搜索树
一、题目描述
给你二叉搜索树的根节点 root ,该树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。
示例 1: 输入:root = [1,3,null,null,2] 输出:[3,1,null,null,2] 解释:3 不能是 1 左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2: 输入:root = [3,1,4,null,null,2] 输出:[2,1,4,null,null,3] 解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
提示:
树上节点的数目在范围 [2, 1000]
内
-2^31 <= Node.val <= 2^31 - 1
二、解题思路
我们需要考虑两个节点被错误地交换后对原二叉搜索树造成了什么影响。对于二叉搜索树,我们知道如果对其进行中序遍历,得到的值序列是递增有序的,而如果我们错误地交换了两个节点,等价于在这个值序列中交换了两个值,破坏了值序列的递增性。
我们来看下如果在一个递增的序列中交换两个值会造成什么影响。假设有一个递增序列a=[1,2,3,4,5,6,7]。如果我们交换两个不相邻的数字,例如 2 和 6,原序列变成了 a=[1,6,3,4,5,2,7],那么显然序列中有两个位置不满足ai<ai+1,在这个序列中体现为 6>3,5>2,因此只要我们找到这两个位置,即可找到被错误交换的两个节点。如果我们交换两个相邻的数字,例如 2 和 3,此时交换后的序列只有一个位置不满足 ai <ai+1。因此整个值序列中不满足条件的位置或者有两个,或者有一个。
至此,解题方法已经呼之欲出了:
找到二叉搜索树中序遍历得到值序列的不满足条件的位置。 如果有两个,我们记为 i 和 j(i<j 且 ai>ai+1 && aj>aj+1),那么对应被错误交换的节点即为 ai对应的节点和aj+1对应的节点,我们分别记为 x 和 y。 如果有一个,我们记为 i,那么对应被错误交换的节点即为ai对应的节点和ai+1对应的节点,我们分别记为 x 和 y。 交换 x 和 y 两个节点即可。 实现部分,本方法开辟一个新数组nums 来记录中序遍历得到的值序列,然后线性遍历找到两个位置 i 和 j,并重新遍历原二叉搜索树修改对应节点的值完成修复,具体实现可以看下面的代码。
三、代码
class Solution {
public void recoverTree(TreeNode root) {
List<Integer> nums = new ArrayList<Integer>();
inorder(root, nums);
int[] swapped = findTwoSwapped(nums);
recover(root, 2, swapped[0], swapped[1]);
}
public void inorder(TreeNode root, List<Integer> nums) {
if (root == null) {
return;
}
inorder(root.left, nums);
nums.add(root.val);
inorder(root.right, nums);
}
public int[] findTwoSwapped(List<Integer> nums) {
int n = nums.size();
int x = -1, y = -1;
for (int i = 0; i < n - 1; ++i) {
if (nums.get(i + 1) < nums.get(i)) {
y = nums.get(i + 1);
if (x == -1) {
x = nums.get(i);
} else {
break;
}
}
}
return new int[]{x, y};
}
public void recover(TreeNode root, int count, int x, int y) {
if (root != null) {
if (root.val == x || root.val == y) {
root.val = root.val == x ? y : x;
if (--count == 0) {
return;
}
}
recover(root.right, count, x, y);
recover(root.left, count, x, y);
}
}
}
四、复杂度分析
时间复杂度:O(N),其中 N 为二叉搜索树的节点数。中序遍历需要 O(N) 的时间,判断两个交换节点在最好的情况下是 O(1),在最坏的情况下是 O(N),因此总时间复杂度为 O(N)。 空间复杂度:O(N)。我们需要用nums 数组存储树的中序遍历列表。
相关文章
- 程序员编程生涯中常会犯的7个错误
- 如何用Go语言每分钟处理100万个请求
- 想成为牛逼程序员? 先数数编程语言之父们的头发
- 日常Bug排查-抛异常不回滚
- 程序员如何用一个脚本每天定时给多个女友发微信暖心话
- 线程池的使用场景和代码实现!
- 为什么很多高校将c语言作为编程入门语言
- Python Web框架:Django vs Flask vs Pyramid
- 一个地区问题引发的一些列思考
- 写的代码又被喷?8招让你的代码更Pythonic
- Go语言在扫码支付系统中的成功实践
- 前端如何解决跨域问题?
- 如何用状态机简化代码中复杂的 If Else 逻辑
- 鸿蒙轻内核M核源码分析系列十三 消息队列Queue
- 基于C++ 语言库的GCC和Clang编译器基准测试报告(ETL)
- 鸿蒙轻内核M核源码分析系列十二事件Event
- 一篇文章带你了解JavaScript switch
- 通向微服务的第一关,这几点摸透了少踩坑!
- 韩信拜将:委派模式
- 别再像2009年那样写PHP代码了