我要评论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
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论