力扣 【99. 恢复二叉搜索树】Java题解(二叉树的 Morris 遍历)

题目链接

Morris遍历

递归和迭代遍历，不管是前序中序还是后续，空间复杂度都是O(n)（递归是因为隐式调用栈的开销）。
而Morris遍历可以做到空间复杂度是O(1)。
思路就是节点的前序节点的右指针指向该节点，来保证可以通过前序节点找到后一个节点。
代码如下：

过程图如下：

思路

通过Morris遍历，我们就可以做到O(1)的空间复杂度中序遍历这个二叉树。
然后在中序遍历的序列找到错误的节点的方法是找到降序的段。
这里借用了一个视频的一张图：我们可以发现如果只有一个降序段，那就交换这两个节点；如果有两个降序段，就交换第一个段的左边节点和第二个段的右边节点即可。

代码

class Solution {
    TreeNode x,y; //要交换的两个节点
    TreeNode preNode; //前一个节点
    boolean flag = false; //判断是第一次还是第二次降序的标志
    public void recoverTree(TreeNode root) {
        TreeNode cur = root;
        while(cur != null){
            if(cur.left == null){
                check(preNode,cur);
                preNode = cur;
                cur = cur.right;
            }else{
                TreeNode temp = cur.left;
                while(temp.right != null && temp.right != cur){
                    temp = temp.right;
                }
                if(temp.right == null){
                    temp.right = cur;
                    cur = cur.left;
                }else{
                    check(preNode,cur);
                    temp.right = null;
                    preNode = cur;
                    cur = cur.right;
                }
            }
        }
        swap(x,y);
    }
    public void swap(TreeNode x,TreeNode y){
        int t = x.val;
        x.val = y.val;
        y.val = t;
    }
    public void check(TreeNode preNode,TreeNode cur){
        if(preNode != null && preNode.val > cur.val){
            if(!flag){
                x = preNode;
                y = cur;
                flag = true;
            }else{
                y = cur;
            }
        }
    }
}

相关题目：
https://leetcode.cn/problems/find-mode-in-binary-search-tree

参考：
https://mp.weixin.qq.com/s?__biz=MzI5ODA5NTgyMw==&mid=2247483907&idx=1&sn=0244e1276e31e0ee55a42601158e7481&chksm=ecaa47a3dbddceb5c49e67fbbfd8f2d4ddd1f902e83bdc6114068a7165cf937281eebf35e4c4&token=1538071990&lang=zh_CN#rd