莫里斯算法

1、二叉树的遍历

对于二叉树的遍历分为三种：前序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)。假设一个树高为h的二叉树，三种遍历算法的时间复杂度都是O(n)，空间复杂度为O(h) 因为遍历二叉树的每一个节点，最好的情况就是每一个节点被访问一次，所以时间复杂度无法再优化，但是空间复杂度仍然可以优化。二叉树的遍历算法可以使用递归和非递归来实现，递归会有隐式的调用堆栈，非递归使用额外的数据结构来支持。

哪如何在遍历过程中避免去申请额外的空间呢？我们知道对于一个拥有n个节点的二叉树，有2n个指针域，但是非空指针域有n-1个，空指针域有n+1个，这些空指针域能不能拿来用呢？线索二叉树就是首先对一棵二叉树变成一棵线索二叉树，线索二叉树就是将左孩子空指针域指向其前驱节点，右孩子空指针域指向其后继节点，莫里斯算法就是基于线索二叉树来实现O(1)空间复杂度的遍历。

2、莫里斯算法思想

我们有下面的二叉树: 如果采用中序遍历，顺序为: 1,2,3,4,5,6,7,8,9,10

2.1 线索二叉树

我们首先将该二叉树变成线索二叉树如下: 可以看到对于节点的空指针域用来指向其前驱和后继节点，这样就将闲置的空间利用起来了，而不用堆栈保存上一层节点的位置，节省了空间。

2.2 前序节点

如何寻找前序节点？如果当前节点有左孩子，那么从左孩子开始一直沿着右孩子指针一直往右走，直到走到叶子节点为止，该叶子节点即为当前节点的前序节点，例如节点6，首先移动到左孩子4，然后从该节点的右孩子移动到叶子节点5，5即是节点6的前序节点。

2.3 莫里斯中序遍历

根据当前节点，找到其前序节点，如果该前序节点右孩子为空，咋将前序节点的右孩子指向当前节点，然后进入当前节点的左孩子;

如果当前节点的左孩子为空，访问该节点，然后进入其右孩子;

如果当前节点的前序节点的右孩子指向自身，将前序节点的右孩子设置为null，访问该节点，然后进入其右孩子。

3、实现

// 获取前序节点
public TreeNode getPredecessor(TreeNode root){
    TreeNode pre = root;
    if (root.left != null){
        pre = pre.left;
        // 一直往右孩子移动
        while (pre.right != null && pre.right != root){
            pre = pre.right;
        }
    }

    return pre;
}

// 莫里斯中序遍历
public void morrisTravel(TreeNode root){
    while (root != null){
        if(root.left == null){
            // 打印当前节点
            System.out.println(root.val);
            // 进入到右孩子
            root = root.right;
        }else {
            // 找到当前节点的前序节点
            TreeNode pre = getPredecessor(root);
            // 如果前序节点的右孩子为null，将右孩子指向当前节点
            if (pre.right == null){
                pre.right = root;
                root = root.left;
            }else if (pre.right == root){
                pre.right = null;
                System.out.println(root.val);
                root = root.right;
            }
        }
    }
}