Morris 遍历

概述

一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1)。通过利用原树中大量空闲右指针的方式，达到节省空间的目的。
Morris的本质是线索二叉树（Threaded Bianry Tree）。本质是利用二叉树中n+1个指向NULL的指针。
Morris遍历的关键
- 利用一棵树上大量的右指针空闲空间
Morris遍历细节
- 假如现在有个当前节点cur，开始时cur再root的位置
- 1.如果cur没有左孩子，cur向右移动
- 2.如果cur有左孩子，找到左子树上最右的节点 mostRight
  - a.如果mostRight.right为null，就让其指向cur，也就是mostRight.right=cur,然后cur向左移动cur=cur.left。
  - b.如果mostRight.right=cur,则让其指向null，然后cur向右移动cur=cur.right.
  - 3.cur为空时遍历停止。
morris序
- 任何结点只要有左树，都会来两次，而且是在遍历完左树后，第二次回到这个结点；如果某个结点没有左树，只会到一次。

应用

Morris 先序遍历

思路：对于能回到自己两次的结点，在第一次到的时候就处理;对于只会到达一次的结点，就直接处理

public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> stoge = new ArrayList<Integer>();
       TreeNode mostRight=null;
       TreeNode cur=root;
       if(root==null){
           return stoge;
       }
       while(cur!=null){
           mostRight=cur.left;
           if(mostRight!=null){
               while(mostRight.right!=null&&mostRight.right!=cur){
                   mostRight=mostRight.right;
               }
               if(mostRight.right==null){
                   stoge.add(cur.val);
                   mostRight.right=cur;
                   cur=cur.left;
                   continue;
               }
               else{
                   mostRight.right=null;
               }
           }
               else{
                   stoge.add(cur.val);
               }
               cur=cur.right;
           }
           return stoge;
       }

Morris 中序遍历

思路：对于能回到自己两次的结点，在第二次到的时候就处理；对于只会到达一次的结点就直接处理

public List<Integer> inorderTraversal(TreeNode root) {
       List<Integer> storage = new ArrayList<Integer>();
       Stack<TreeNode> visit = new Stack<TreeNode>();
       TreeNode cur = root;
       while(cur!=null||!visit.isEmpty()){
           if(cur!=null){
               visit.push(cur);
               cur=cur.left;
           }
           else{
               cur=visit.pop();
               storage.add(cur.val);
               cur=cur.right;
           }
       }
       return storage;
   }

Morris 后序遍历

思路：把处理的时机放在能回到自己两次的结点，并且是第二次回到自己的时候，但是不打印自己，而是逆序打印自己左子树的右边界。最后，Morris遍历完后，逆序打印整棵树的右边界。

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> stoge = new ArrayList<Integer>();
        Stack<Integer> visit = new Stack<Integer>();
        TreeNode cur = root,mostRight =null;
        if(cur==null){
            return stoge;
        }
        while(cur!=null){
            mostRight=cur.left;
            if(mostRight!=null){
                while(mostRight.right!=null&&mostRight.right!=cur){
                    mostRight=mostRight.right;
                }
                if(mostRight.right==null){
                    mostRight.right=cur;
                    cur=cur.left;
                    continue;
                }else{
                    mostRight.right=null;
                    addPath(stoge,cur.left);
                }
            }
            cur=cur.right;
        }
        addPath(stoge,root);
        return stoge;
    }
    public void addPath(List<Integer>stoge,TreeNode node){
        int count = 0;
        while(node!=null){
            ++count;
            stoge.add(node.val);
            node=node.right;
        }
        int left = stoge.size()-count,right = stoge.size()-1;
        while(left<right){
            int temp = stoge.get(left);
            stoge.set(left,stoge.get(right));
            stoge.set(right,temp);
            left++;
            right--;
        }
    }

问题：

问题1：逆序打印一棵树的右边界，是不是一定得用到栈呢？？？
- 答：其实还有一种方法，那就是链表反转。
问题2：Morris遍历它的每到一个结点，都会遍历该结点左子树的右边界两次，那么它的时间复杂度还会使O(n)吗？
- 答：所有的左子树的右边界都是不重复的，也就是说，所有结过它左子树的有边界的时间复杂度也就是整棵树的规模而已。