LeetCode 99. 恢复二叉搜索树
程序员文章站
2022-04-11 22:00:50
LeetCode 99. 恢复二叉搜索树题目99. 恢复二叉搜索树二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。示例 1:输入: [1,3,null,null,2] 1 / 3 \ 2输出: [3,1,null,null,2] 3 / 1 \ 2示例 2:输入: [3,1,4,null,null,2] 3 / \1 4 / 2输出: [2,1,4,null,null,3]...
LeetCode 99. 恢复二叉搜索树
题目
99. 恢复二叉搜索树
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下,恢复这棵树。
示例 1:
输入: [1,3,null,null,2]
1
/
3
\
2
输出: [3,1,null,null,2]
3
/
1
\
2
示例 2:
输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
思路
很简单,因为用容器存储后,检查逆序对,需要存储所有数据,故,如果使用bfs或dfs重建需要on的空间复杂度。
如果要o1的话,就只能用头尾节点的方式进行操作,很明显,需要将一个链表进行人体蜈蚣。从思维上来说就是,如果一
个节点第二次被访问,那么他肯定所有左节点已经被检查过了。怎么去检查他是不是第二次访问呢?答,根据搜索二叉树
的性质进行操作,前一个节点的左右子节点肯定是空的,操作就完事。左走无意义。只有当前节点所有左节点走空后,才
会发生能够判断置换的情况。(这里可能有点难以想,下面的代码,为什么人体蜈蚣不会错,因为找左子节点的最右节点
只会找出一个,并且不会指向自己,所以可以通过此来判断是否第二次访问,只要走下去,因为是链表,所以不会出现其
他情况)
class Solution {
public void recoverTree(TreeNode root) {
TreeNode re1=null;
TreeNode re2=null;
TreeNode pre=null;
TreeNode tmp=root;
TreeNode last=null;
while(tmp!=null){
//找到链表的尾巴
last=tmp.left;
if(last!=null){
//链表有左节点
while(last.right!=null &&last.right!=tmp){
last=last.right;
}
if(last.right==null){
//链表末尾没有存储元素,就把头节点放到链表末尾,并在链表的开头把头节点删了
//往左边走都是没有意义的,具体原因自己脑部人体蜈蚣,某一个节点的右子节点的最右手的就是他的前一个数字
//这里相当于就是stack
last.right=tmp;
tmp=tmp.left;
continue;
}else{
//已经对左链表进行了操作,回溯做链表记录末尾的节点,并将问题交给右链表,因为这里是人体蜈蚣,所以直接换就行了
last.right=null;
}
}
//因为只有往右链表走,才是真的有用
if (pre != null && pre.val > tmp.val) {
re2 = tmp;
if (re1 == null) {
re1 = pre;
System.out.println("change 1");
}
}
pre = tmp;
tmp=tmp.right;
}
int a =re2.val;
re2.val=re1.val;
re1.val=a;
}
}
本文地址:https://blog.csdn.net/qq_42499133/article/details/107888930
上一篇: numpy.linspace使用详解
下一篇: 准能生个姚明二代