LeetCode: Recover Binary Search Tree 解题报告
Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
Hide Tags Tree Depth-first Search
SOLUTION 1:
采用递归+全局变量完成:
空间复杂度是O(logn)
REF: http://huntfor.iteye.com/blog/2077665
这一篇讲得蛮清楚:
http://yucoding.blogspot.com/2013/03/leetcode-question-75-recover-binary.html
具体的思路,还是通过中序遍历,只不过,不需要存储每个节点,只需要存一个前驱即可。
例如1,4,3,2,5,6
1.当我们读到4的时候,发现是正序的,不做处理
2.但是遇到3时,发现逆序,将4存为第一个错误节点,3存为第二个错误节点
3.继续往后,发现3,2又是逆序了,那么将第2个错误节点更新为2
如果是这样的序列:1,4,3,5,6同上,得到逆序的两个节点为4和3。
========================================
这里我们补充一下,为什么要替换第二个节点而不是第一个节点:
e.g. The correct BST is below:
The inorder traversal is : 1 3 4 6 7 8 10 13
14
Find the place which the order is wrong.
Wrong order: 1 3 8 6 7 4 10 13
14
FIND:
8 6
Then we
find:
7 4
8, 6 是错误的序列, 但是,7,4也是错误的序列。
因为8,6前面的序列是正确的,所以8,6一定是后面的序列交换来的。
而后面的是比较大的数字,也就是说8一定是被交换过来的。而7,4
中也应该是小的数字4是前面交换过来的。
用反证法来证明:
假设:6是后面交换过来的
推论: 那么8比6还大,那么8应该也是后面交换来的,
这样起码有3个错误的数字了
而题目是2个错误的数字,得证,只应该是8是交换过来的。
结论就是:我们需要交换的是:8, 4.
public class RecoverTree {
TreeNode pre = null;
TreeNode first = null;
TreeNode second = null; public void recoverTree(TreeNode root) {
inOrder(root); // swap the value of first and second node.
int tmp = first.val;
first.val = second.val;
second.val = tmp;
} public void inOrder(TreeNode root) {
if (root == null) {
return;
} // inorder traverse.
inOrder(root.left); /*
Find the place which the order is wrong.
For example: 1 3 4 6 7 8 10 13 14
Wrong order: 1 3 8 6 7 4 10 13 14
FIND: ___
Then we find: ___
8, 6 是错误的序列, 但是,7,4也是错误的序列。
因为8,6前面的序列是正确的,所以8,6一定是后面的序列交换来的。
而后面的是比较大的数字,也就是说8一定是被交换过来的。而7,4
中也应该是小的数字4是前面交换过来的。 用反证法来证明:
假设:6是后面交换过来的
推论: 那么8比6还大,那么8应该也是后面交换来的,
这样起码有3个错误的数字了
而题目是2个错误的数字,得证,只应该是8是交换过来的。
*/ // 判断 pre 是否已经设置
if (pre != null && pre.val > root.val) {
if (first == null) {
// 首次找到反序.
first = pre;
second = root;
} else {
// 第二次找到反序,更新Second.
second = root;
}
} pre = root; // inorder traverse.
inOrder(root.right);
}
SOLUTION 2:
也可以采用非递归方法,不需要加全局变量,空间复杂度是O(logn):
public void recoverTree1(TreeNode root) {
if (root == null) {
return;
} TreeNode node1 = null;
TreeNode node2 = null; TreeNode pre = null; Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode cur = root; while (true) {
while (cur != null) {
s.push(cur);
cur = cur.left;
} if (s.isEmpty()) {
break;
} TreeNode node = s.pop(); if (pre != null) {
// invalid order
if (pre.val > node.val) {
if (node1 == null) {
node1 = pre;
node2 = node;
} else {
node2 = node;
}
}
} pre = node; cur = node.right;
} int tmp = node1.val;
node1.val = node2.val;
node2.val = tmp; return;
}
SOLUTION 3:
还有更厉害的作法,可以达到O(1)的空间复杂度。以后再补上。
ref: http://fisherlei.blogspot.com/2012/12/leetcode-recover-binary-search-tree.html
=================
代码请参考主页君的实现:
请戳主页君的代码哦
最新文章
- WPF中弹出菜单
- R语言将字符串矩阵转化为数值型矩阵
- Linux C编程(2) dgb调试
- 本地数据下,radiobutton和图片组合,利用adapter+listview进行单选
- Swift语言实战晋级-第9章 游戏实战-跑酷熊猫-4 熊猫的跳和打滚
- RAR暴破
- 【转】linux root用户ifconfig报command not found
- CentOS 7:如何安装防火墙?
- KMP笔记√//找最大子串,前缀自匹配长度
- Python设计模式——观察者模式
- mit java open course assignment #2
- Java基础学习
- 使用ML.NET实现德州扑克牌型分类器
- Code once, debug everywhere.
- browserify babel gulp 没有编译import的文件
- 【转】C# Enum,Int,String的互相转换 枚举转换
- 盲刷bios
- 1090. Highest Price in Supply Chain (25)-dfs求层数
- WPF中的3D变换PlaneProjection
- css小点心
热门文章
- C++语言实现-邻接矩阵
- 用VScode来编写C / C ++代码
- 洛谷 P1474 货币系统 Money Systems(经典)【完全背包】+【恰好装满的最大方案数量】
- Android 7.0 PopupWindow 又引入新的问题,Google工程师也不够仔细么
- Ubuntu pkg_resources.DistributionNotFound: The &#39;Scrapy==1.0.3&#39; distribution was not found and is required by the application
- C# GUID生成
- JS-排序详解-快速排序
- 探究functools模块wraps装饰器的用途
- 最小生成树之克鲁斯卡尔(kruskal)算法
- 响应式 Web 设计指南「实践篇」