写在前：树的遍历
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; }
