原题链接:http://oj.leetcode.com/problems/recover-binary-search-tree/这道题是要求恢复一颗有两个元素调换错了的二叉查找树。一开始拿到可能会觉得比较复杂,其实观察出规律了就比较简单。主要还是利用二叉查找树的主要性质,就是中序遍历是有序的性质。那么如果其中有元素被调换了,意味着中序遍历中必然出现违背有序的情况。那么会出现几次呢?有两种情况,如果是中序遍历相邻的两个元素被调换了,很容易想到就只需会出现一次违反情况,只需要把这个两个节点记录下来最后调换值就可以;如果是不相邻的两个元素被调换了,举个例子很容易可以发现,会发生两次逆序的情况,那么这时候需要调换的元素应该是第一次逆序前面的元素,和第二次逆序后面的元素。比如1234567,1和5调换了,会得到5234167,逆序发生在52和41,我们需要把4和1调过来,那么就是52的第一个元素,41的第二个元素调换即可。搞清楚了规律就容易实现了,中序遍历寻找逆序情况,调换的第一个元素,永远是第一个逆序的第一个元素,而调换的第二个元素如果只有一次逆序,则是那一次的后一个,如果有两次逆序则是第二次的后一个。算法只需要一次中序遍历,所以时间复杂度是O(n),空间是栈大小O(logn)。代码如下:public void recoverTree(TreeNode root) {
if(root == null)
return;
ArrayList<TreeNode> pre = new ArrayList<TreeNode>();
pre.add(null);
ArrayList<TreeNode> res = new ArrayList<TreeNode>();
helper(root,pre, res);
if(res.size()>0)
{
int temp = res.get(0).val;
res.get(0).val = res.get(1).val;
res.get(1).val = temp;
}
}
private void helper(TreeNode root, ArrayList<TreeNode> pre, ArrayList<TreeNode> res)
{
if(root == null)
{
return;
}
helper(root.left, pre, res);
if(pre.get(0)!=null && pre.get(0).val>root.val)
{
if(res.size()==0)
{
res.add(pre.get(0));
res.add(root);
}
else
{
res.set(1,root);
}
}
pre.set(0,root);
helper(root.right,pre,res);
}
可以看到实现中pre用了一个ArrayList来存,这样做的原因是因为java都是值传递,所以我们要全局变化pre的值(而不是在当前函数里),只能传一个数组,才能改变结点的地址,这一点非常重要,也是java和C++一个比较大的区别,不了解的朋友可以研究一下哈。这道题还是考察二叉树遍历,不过应用题目要求套了一个不同的外壳,需要我们利用二叉查找树的性质观察出规律之后才能求解。
分享到:
相关推荐
Recover Binary Search Tree - Java Recursive 0101 Symmetric tree - Java Recursive - Java Iterative - C Recursive - Python Iterative 0102 Binary Tree Level Order Traversal - Python3 iterative 0103...
利用先序,中序遍历恢复二叉树 ,用兴趣的朋友可以看一下
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
lru缓存leetcode leetcode 大批 41. First Missing Positive 广度优先搜索 ...Recover Binary Search Tree 109. Convert Sorted List to Binary Search Tree 116. Populating Next Right Pointers in Each No
RecoverMyFiles是常用的文件恢复工具,其特点:可按分区按文件类型恢复
Recover Password FANUC PMC-2020_PMCpassword_Mohsen_dearifx_fanucpmc_fanuc_源码.rar
Recover Password FANUC PMC-2020_PMCpassword_Mohsen_dearifx_fanuc
Using unique option prefix myisam_recover instead of myisam-recover-options is deprecated and will be removed in a future release. Please use the full name instead
Recover Binary Search Tree Same Tree Symmetric Tree Balanced Binary Tree Flatten Binary Tree to Linked List Populating Next Right Pointers in Each Node II 二叉树的构建 Construct Binary Tree from ...
数据文件恢复 绿色软件
资料恢复 软件已经破解,注册时注册名和注册码任意,开心使用吧!
RecoverMyFiles-Setup
电脑软件数据恢复Wondershare-Recoverit-8.2.0.17
这是朋友给我的,停不错的,对由于勿删除的东西恢复很好用!
万兴数据恢复Wondershare-Recoverit-8.2.0.17.rar
Recover My Files 序列号.txt
各类实用工具,经测试,需要的下载