欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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