递归解法（不需要太过于在意具体的递归过程，而是要想清楚让计算机干什么。）
前序遍历
public static void preOrderRecur(TreeNode head) { if (head == null) { return; } System.out.print(head.value + " "); preOrderRecur(head.left); preOrderRecur(head.right);}
中序遍历
public static void preOrderRecur(TreeNode head) { if (head == null) { return; } preOrderRecur(head.left); System.out.print(head.value + " "); preOrderRecur(head.right);}
后序遍历
public static void postOrderRecur(TreeNode head) { if (head == null) { return; } postOrderRecur(head.left); postOrderRecur(head.right); System.out.print(head.value + " ");}
|
迭代解法（本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用Stack来模拟系统栈。）
前序遍历
public static void preOrderIteration(TreeNode head) { if (head == null) { return; } Stack<TreeNode> stack = new Stack<>(); stack.push(head); while (!stack.isEmpty()) { TreeNode node = stack.pop(); System.out.print(node.value + " "); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } }}
中序遍历
public static void inOrderIteration(TreeNode head) { if (head == null) { return; } TreeNode cur = head; Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || cur != null) { while (cur != null) { stack.push(cur); cur = cur.left; } TreeNode node = stack.pop(); System.out.print(node.value + " "); if (node.right != null) { cur = node.right; } }}
后序遍历
public static void postOrderIteration(TreeNode head) { if (head == null) { return; } Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); stack1.push(head); while (!stack1.isEmpty()) { TreeNode node = stack1.pop(); stack2.push(node); if (node.left != null) { stack1.push(node.left); } if (node.right != null) { stack1.push(node.right); } } while (!stack2.isEmpty()) { System.out.print(stack2.pop().value + " "); } }
或
public static void postOrderIteration2(TreeNode head) { if (head == null) { return; } TreeNode cur = head; Stack<TreeNode> stack = new Stack<>(); stack.push(head); while (!stack.isEmpty()) { TreeNode peek = stack.peek(); if (peek.left != null && peek.left != cur && peek.right != cur) { stack.push(peek.left); } else if (peek.right != null && peek.right != cur) { stack.push(peek.right); } else { System.out.print(stack.pop().val + " "); cur = peek; } }}
|
Morris解法
Morris遍历使用二叉树节点中大量指向null的指针，由Joseph Morris 于1979年发明。
时间复杂度：O(n)O(n)O(n)
额外空间复杂度：O(1)O(1)O(1)
模板代码
public static void preOrderMorris(TreeNode head) { if (head == null) { return; } TreeNode cur1 = head; TreeNode cur2 = null; while (cur1 != null) { cur2 = cur1.left; if (cur2 != null) { while (cur2.right != null && cur2.right != cur1) { cur2 = cur2.right; } if (cur2.right == null) { cur2.right = cur1; cur1 = cur1.left; continue; } else { cur2.right = null; } } cur1 = cur1.right; }}
前序遍历
public static void preOrderMorris(TreeNode head) { if (head == null) { return; } TreeNode cur1 = head; TreeNode cur2 = null; while (cur1 != null) { cur2 = cur1.left; if (cur2 != null) { while (cur2.right != null && cur2.right != cur1) { cur2 = cur2.right; } if (cur2.right == null) { cur2.right = cur1; System.out.print(cur1.value + " "); cur1 = cur1.left; continue; } else { cur2.right = null; } } else { System.out.print(cur1.value + " "); } cur1 = cur1.right; }}
中序遍历
public static void inOrderMorris(TreeNode head) { if (head == null) { return; } TreeNode cur1 = head; TreeNode cur2 = null; while (cur1 != null) { cur2 = cur1.left; if (cur2 != null) { while (cur2.right != null && cur2.right != cur1) { cur2 = cur2.right; } if (cur2.right == null) { cur2.right = cur1; cur1 = cur1.left; continue; } else { cur2.right = null; } } System.out.print(cur1.value + " "); cur1 = cur1.right; }}
后序遍历
public static void postOrderMorris(TreeNode head) { if (head == null) { return; } TreeNode cur1 = head; TreeNode cur2 = null; while (cur1 != null) { cur2 = cur1.left; if (cur2 != null) { while (cur2.right != null && cur2.right != cur1) { cur2 = cur2.right; } if (cur2.right == null) { cur2.right = cur1; cur1 = cur1.left; continue; } else { cur2.right = null; postMorrisPrint(cur1.left); } } cur1 = cur1.right; } postMorrisPrint(head);}public static void postMorrisPrint(TreeNode head) { TreeNode reverseList = postMorrisReverseList(head); TreeNode cur = reverseList; while (cur != null) { System.out.print(cur.value + " "); cur = cur.right; } postMorrisReverseList(reverseList);}public static TreeNode postMorrisReverseList(TreeNode head) { TreeNode cur = head; TreeNode pre = null; while (cur != null) { TreeNode next = cur.right; cur.right = pre; pre = cur; cur = next; } return pre;}
后序遍历较为复杂：
|
当我们到达最左侧，也就是左边连线已经创建完毕了。
打印 4
打印 5 2
打印 6
打印 7 3 1
我们将一个节点的连续右节点当成一个单链表来看待。
当我们返回上层之后，也就是将连线断开的时候，打印下层的单链表。
比如返回到 ２，此时打印 ４
比如返回到 １，此时打印 ５ ２
比如返回到 ３，此时打印 ６
那么我们只需要将这个单链表逆序打印就行了，下文也给出了 单链表逆序代码
这里不应该打印当前层，而是下一层，否则根结点会先与右边打印。
