[数据结构与算法]morris算法遍历二叉树

morris遍历时二叉树遍历的一种更高效的方式。其他基础的二叉树遍历不在这里赘述。
二叉树的前中后序，层序遍历详解

morris遍历可以达到空间复杂度O(1)，时间复杂度O(2n)

morris遍历过程：

1. 如果cur.left == null,直接cur = cur.right
2. 如果cur.left != null,就找到左子树中最右的结点，记做mostRight。
3. 如果mostRight.right == cur ,则将mostRight.right = null，然后cur = cur.right
4. 将mostRight.right = null, 则将mostRight.right = cur, 然后cur = cur.left

过程解释（中序为例）：

1. 其实是巧用叶子结点的空闲指针，来代替递归。遍历二叉树的过程是 左子树-跟结点-右子树。所以morris算法中，再遍历左子树之前，将左子树中最右的结点的right指向跟结点，就可以再遍历完左子树之后，回到跟结点。
2. 回到跟结点的时候，再将那个辅助指向删除，然后再去遍历右子树即可。
3. 通过过程可以知道每个节点都达到过两次（第二次是去验证并删除指向的时候）

代码：

• morris最好的实现只有前序和中序遍历。因为后序的话要回到跟结点两次。就达不到O(2n)的效果。

//morris前序遍历
    private static void morrisProOrder(Node head) {
        if (head == null) return;
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            System.out.print(cur.val + " ");
            mostRight = cur.left;
            if (mostRight != null) {//如果左子树存在
                while (mostRight.right != null && mostRight.right != cur.right) {//找到左子树中最右的结点
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {//说明左子树还没有遍历过
                    mostRight.right = cur.right;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;//删除这个辅助结点
                }
            }
            cur = cur.right;
        }
    }

    //中序
    private static void morrisMidOrder(Node head) {
        if (head == null) return;
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            //首先找到当前结点的左子树的最右节点,前提是左子树不为空
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == cur) { //表示左子树已经遍历完
                    mostRight.right = null;
                } else {//找到这个元素后，将right指向当前结点，然后再同样的方式去找当前结点的left
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }
            }
            //左子树为空就可以通过right域打印了
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
    }