Morris遍历二叉树

前言

• 对于二叉树的遍历，递归的前、中、后序遍历可以说是最经典、最简单的，其次，非递归版的就是手动压栈的方式模拟递归的过程。
• 而Morris遍历是一种通过修改二叉树本身的结构从而实现常数级空间的遍历方法，估计很多人没见过，可以说是装逼利器。

Morris遍历过程

假设遍历到当前节点cur

• 如果cur节点没有左子树，cur指针右移，cur = cur.right
• 如果cur节点有左子树，找到cur节点的左子树的最右节点，记为mostRight
  • 如果mostRight节点的右指针为空，则将其指向cur，cur指针左移，cur = cur.left
  • 如果mostRight节点的右指针指向cur，则将其指向空，cur指针右移，cur = cur.right

例

如上图的一棵二叉树，

• cur指针从根节点开始遍历，如图1，cur指向根节点，此时找到它的左子树的最右节点7，因mostRight == null，所以将它的右指针指向cur，然后cur左移。
• 图2同理，节点3作为以根节点为5的子树的mostRight，让它的右指针指向节点5
  
• 然后来到节点3，节点3没有左子树，则cur指针右移，回到节点5。
• 节点5又找它的左子树的最右节点，此时最右节点的右指针指向cur，则将其右指针指向空，cur右移

综合以上遍历过程，走过的节点顺序为
10 - > 5 -> 3 -> 5 -> 7 -> 10 - > 15 - > 18
可以看出，如果一个节点有左子树，它会被经过两次，反之，只会经过一次(也可以理解为两次重叠)。因为有左子树，才能被左子树的最右节点的右指针指向，没有左子树自然没有，回不来。

Morris前序遍历

在递归版遍历二叉树时，所谓的前序、中序、后续遍历不过是在处理数据的时机不同。Morris遍历也是如此。
如果我们在第一次遍历到节点时就对节点进行操作，就是前序遍历了。
判断第一次来到节点cur的依据：

• mostRight == null
• 没有左子树

leetcode 144. 二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//Morris先序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        
        TreeNode cur = root;
        TreeNode mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                //找到mostRight，如果是第二次来到cur，mostRight还可能指向cur
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                //如果mostRight.right == null，说明是第一次来到cur
                if(mostRight.right == null){
                    list.add(cur.val);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                //第二次来到`cur`，将mostRight.right还原
                }else{
                    mostRight.right = null;
                }
            //没有左子树
            }else{
                list.add(cur.val);
            }
            cur = cur.right;
        }
        return list;
    }
}

Morris中序遍历

中序遍历很简单，就是在cur指针向右移之前做操作。
leetcode 94. 二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        
        TreeNode cur = root;
        TreeNode mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                //找到mostRight，如果是第二次来到cur，mostRight还可能指向cur
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                //如果mostRight.right == null，说明是第一次来到cur
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                //第二次来到`cur`，将mostRight.right还原
                }else{
                    mostRight.right = null;
                }
            }
            list.add(cur.val);
            cur = cur.right;
        }
        return list;
    }
}

Morris后序遍历

二叉树可以被右边界划分，如下图所示

• 每当第二次经过一个节点，逆序打印它的左子树，得到的结果就是后序遍历的结果。
  如上图的结果就是3 -> 7 -> 5 -> 1 -> 18 -> 15 -> 10

二叉树的右边界逆序

• 初始状态，定义两个指针p和q，让p遍历右边界，q指向已遍历部分的最后一个节点
• 在将p.right指向q时，需要用x记录下p本来的right

TreeNode p = head.right;
        TreeNode q = head;
        head.right = null;
        //逆序
        while(p != null){
            TreeNode x = p.right;
            p.right = q;
            q = p;
            p = x;
        }

145. 二叉树的后序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        
        TreeNode cur = root;
        TreeNode mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                //找到mostRight，如果是第二次来到cur，mostRight还可能指向cur
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                //如果mostRight.right == null，说明是第一次来到cur
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                //第二次来到`cur`，将mostRight.right还原
                }else{
                    mostRight.right = null;
                    printEdge(cur.left, list);
                }
            }
            cur = cur.right;
        }
        printEdge(root, list);
        return list;
    }
    private void printEdge(TreeNode head, List<Integer> list){
        TreeNode p = head.right;
        TreeNode q = head;
        head.right = null;
        //逆序
        while(p != null){
            TreeNode x = p.right;
            p.right = q;
            q = p;
            p = x;
        }
        p = q;
        while(p != null){
            list.add(p.val);
            p = p.right;
        }
        p = q.right;
        q.right = null;
        //逆回来
        while(p != null){
            TreeNode x = p.right;
            p.right = q;
            q = p;
            p = x;
        }
    }
}

复杂度分析

• 时间复杂度 O(n)
• 空间复杂度 O(1)