树交换节点与Morris中序遍历

前言

本文从一道leetcode题入手，来介绍常用的Morris中序遍历，与各位一起学习。Morris中序遍历时间复杂度为O(2n)，空间复杂度为O(1)。

恢复二叉搜索树题目描述

二叉树中两个节点的值被错误的交换，恢复这个数

分析

根据二叉搜索树的性质可以得知，我们可以将一个正确的搜索树通过中序遍历退化成升序序列。又由题干得知，假设被交换的两个节点下标分别为i，j。且$i<j$。那么可以得到$x_(i-1)<x_(i)>x_(i+1)$，和$x_{j-1}>x{j}<x{j+1}$，其中我们只需要拿到$x_(k)>x_(k+1)$的下标就可以了。

其中分为两种情况，如果有两个k，那么第一个k为i，第二个k+1为j；如果只有一个k，说明正好他们两个相邻的点进行交换，及k=i，k+1=j。

我们只需要把i，j节点的值进行交换即可解决这道题。

中序遍历，我们可以通过递归的方式，采用DFS遍历，迭代的方式我们也可以通过构造栈的方法进行。本文介绍一个在过程中修改树结构的方法，能够实现常数空间复杂度。

我们继续分析这道题发现实际上我们只需要暂时保存两个节点的地址即可，即当前节点与前一个节点。我们可以用一种能够在常数空间复杂度内做中序遍历的方法进行遍历即可。

可以使用Morris中序遍历算法。

Morris中序遍历

Morris中序遍历的思想，提炼出来只有一个，在中序遍历第一次便利到自己的时候，将当前节点的前继节点的right指向自己。

具体方法如下：

1. 假设当前节点为root，目前有一下两种情况：
2. 如果root的left节点为空，那么直接中序遍历到自己（root），将root指向root.right；
3. 如果root的left节点不为空。先去找到root.left的最右子节点predecessor。然后将predecessor的right指向root节点。然后将root更新为root.left；开始下一步；
   1. 如果root不等于pre.right。即pre不是predecessor，那么回到步骤二；
   2. 如果root==pre.right，说明root.left全部遍历完，此时遍历到了root自己，那么将pre.right还原回null，将root指向root.right即可。

解法

通过Morris遍历的方法我们能够拿到pre和current节点，即前继节点和当前节点。把满足$x_(k)>x_(k+1)$的两个节点引用拿到，再进行交换即可。

算法代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void recoverTree(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode pre = null;
        TreeNode i = null, j = null;
        TreeNode ij1 = null;
        TreeNode predecessor = null;
        int temp = 0;
        while (root != null) {
            if (root.left == null) {
                if (pre != null) {
                    if (pre.val > root.val) {
                        if (temp == 0) {
                            i = pre;
                            ij1 = root;
                            temp++;
                        } else {
                            j = root;
                        }
                    }
                }
                pre = root;
                root = root.right;
            } else {
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }
                if (predecessor.right == null) {
                    predecessor.right = root;
                    root = root.left;
                } else {
                    if (pre != null) {
                        if (pre.val > root.val) {
                            if (temp == 0) {
                                i = pre;
                                ij1 = root;
                                temp++;
                            } else {
                                j = root;
                            }
                        }
                    }
                    pre = root;
                    predecessor.right = null;
                    root = root.right;
                }
            }

        }
        if (j == null) {
            j = ij1;
        }
        var tt = i.val;
        i.val = j.val;
        j.val = tt;
    }
}