二叉树的遍历（递归、迭代和morris多解法）

写在前：树的遍历

        1
       / \
      2   3
     / \   \
    4   5   6

层次遍历顺序：[1 2 3 4 5 6]

morris顺序：[1 2 4 2 5 1 3 6]

前序遍历顺序：[1 2 4 5 3 6]
中序遍历顺序：[4 2 5 1 3 6]
后序遍历顺序：[4 5 2 6 3 1]

层次遍历使用 BFS 实现（另一个场景是求最短路径），利用的就是 BFS 一层一层遍历的特性；

而前序、中序、后序遍历利用了 DFS 实现，前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。

① 前序：

void dfsPre(TreeNode root) {
    if (root == null) return;
    visit(root);
    dfsIn(root.left);
    dfsIn(root.right);
}

② 中序

void dfsIn(TreeNode root) {
    if (root == null) return;
    dfsIn(root.left);
    visit(root);
    dfsIn(root.right);
}

③ 后序

void dfsPos(TreeNode root) {
    if (root == null) return;
    dfsPos(root.left);
    dfsPos(root.right);
    visit(root);
}

morris序

public static void morris(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 == null) {
                mostRight.right = cur;
                cur = cur.left;
                //回到最外层的while情况，继续判断cur的情况
                continue;
            } else {
                mostRight.right = null;
            }
        }
        //没有左孩子
        cur = cur.right;  
    }
}

1.非递归进行二叉树前序遍历（144-中）

思路：

法1：递归是使用系统栈，迭代我们需要自己创建栈模拟这个过程。先序遍历要先记录当前节点值，再依次压如右孩子和左孩子（先进后出）。注：栈结构底层是通过数组实现，可以存储null值。

法2：morris遍历，记录一个节点(出现多次)在morris序中第一次访问的顺序和只出现一次的节点，即左子树的右边界指向null时，我们第一次到达cur节点。

代码：

// 1. 迭代
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.add(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node == null) continue;
        ret.add(node.val);
        stack.push(node.right);
        stack.push(node.left);
    }
    return ret;
}

// 2.morris
public List<Integer> preorderTraversal_1(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    if (root == null) return ret;
    TreeNode cur = root;
    TreeNode mostRight = null;
    
    while (cur != null) {
        mostRight = cur.left;
        if (cur.left != null) {     
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                ret.add(cur.val);   //第一次到达cur
                cur = cur.left;
                continue;
            } else {
                mostRight.right = null;
            }
        } else {
            ret.add(cur.val);      //只到达一次的点
        }
        cur = cur.right;
    }
    return ret;
}

2.非递归进行二叉树后序遍历（145-中）

思路：

法1：反转技巧：前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。

法2：morris遍历：二叉树后序遍历morris改写(逆序打印右边界)。

1、对二叉树遍历中只出现一次的节点，即无左子树的节点，直接跳过
2、对于出现两次的节点，第一次不管，当第二次到达x的时候，逆序打印左子树的右边界
3、遍历完成后，打印整棵树的右边界

代码：

// 1.反转技巧
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.add(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node == null) continue;
        ret.add(node.val);
        stack.push(node.left);
        stack.push(node.right);
    }
    Collections.reverse(ret);
    return ret;
}

// 2. morris
public static void morrisPos(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 == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else {
                mostRight.right = null;  //第二次到达这个位置
                printEdge(cur.left);
            }
        }
        cur = cur.right;
    }
    printEdge(head);    //打印整棵树的右边界
    System.out.println();
}
public static void printEdge(Node head) {
    Node tail = reverseEdge(head);
    Node cur = tail;
    while (cur != null) {
        System.out.print(cur.value + " ");
        cur = cur.right;   //指向前一个节点（逆序）
    }
    reverseEdge(tail);   //打印完成将原结构还原（逆序回去）
}

//逆序右边界
public static Node reverseEdge(Node from) {   //逆序打印左子树的右边界,返回值是节点类型
    Node pre = null;
    Node next = null;
    while (from != null) {
        next = from.right;
        from.right = pre;   //改变指针的方向，指向前一个节点
        pre = from;   //记录前一个节点
        from = next;   //from = from.right
    }
    return pre;   //返回左子树右边界的最后一个元素
}

3.非递归进行二叉树中序遍历（94-中）

思路：

法1：迭代：中序遍历的顺序是【左中右】。每到一个节点node，因为根节点的访问在中间，先将node入栈。先遍历左子树，访问node节点，最后访问右子树。访问完node节点就可以出栈（已经完成左子树和node节点）。注：循环进入条件包括栈非空。

法2：morris遍历，记录一个节点(出现多次)在morris序中第二次访问的顺序和只出现一次的节点，即左子树的右边界指向cur时，我们第二次到达cur节点。

代码：

// 1.迭代
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    if (root == null) return ret;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        // 左子树和node节点已经完成
        TreeNode node = stack.pop();
        ret.add(node.val);
        cur = node.right;
    }   
    return ret; 
}

// 2.morris
public List<Integer> inorderTraversal_1(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    if (root == null) return ret;
    TreeNode cur = root;
    TreeNode mostRight = null;
    while (cur != null) {
        mostRight = cur.left;
        if (cur.left != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;    //左子树最右边界
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;   //回到最外层的while情况，继续判断cur的情况
            } else {
                mostRight.right = null;
            }
        }
        ret.add(cur.val);    //记录只到达一次的点（无左孩子）和第二次到达cur！！！
        cur = cur.right;
    }
    return ret;
}