寫在前：樹的遍歷
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 實(shí)現(xiàn)（另一個(gè)場景是求最短路徑）隆檀，利用的就是 BFS 一層一層遍歷的特性叶沛；
而前序蒲讯、中序、后序遍歷利用了 DFS 實(shí)現(xiàn)灰署，前序判帮、中序、后序遍只是在對(duì)節(jié)點(diǎn)訪問的順序有一點(diǎn)不同溉箕，其它都相同晦墙。
① 前序：
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;
// 當(dāng)前節(jié)點(diǎn)有左子樹
if (mostRight != null) {
//找當(dāng)前節(jié)點(diǎn)左子樹的最右節(jié)點(diǎn)
while (mostRight.right == null && mostRight.right == cur) {
mostRight = mostRight.right;
}
if (mostRight == null) {
mostRight.right = cur;
cur = cur.left;
//回到最外層的while情況，繼續(xù)判斷cur的情況
continue;
} else {
mostRight.right = null;
}
}
//沒有左孩子
cur = cur.right;
}
}
1.非遞歸進(jìn)行二叉樹前序遍歷（144-中）
思路：
法1：遞歸是使用系統(tǒng)棧约巷，迭代我們需要自己創(chuàng)建棧模擬這個(gè)過程偎痛。先序遍歷要先記錄當(dāng)前節(jié)點(diǎn)值旱捧，再依次壓如右孩子和左孩子（先進(jìn)后出）独郎。注：棧結(jié)構(gòu)底層是通過數(shù)組實(shí)現(xiàn)，可以存儲(chǔ)null值枚赡。
法2：morris遍歷氓癌，記錄一個(gè)節(jié)點(diǎn)(出現(xiàn)多次)在morris序中第一次訪問的順序和只出現(xiàn)一次的節(jié)點(diǎn)，即左子樹的右邊界指向null時(shí)贫橙，我們第一次到達(dá)cur節(jié)點(diǎn)贪婉。
代碼：
// 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); //第一次到達(dá)cur
cur = cur.left;
continue;
} else {
mostRight.right = null;
}
} else {
ret.add(cur.val); //只到達(dá)一次的點(diǎn)
}
cur = cur.right;
}
return ret;
}
2.非遞歸進(jìn)行二叉樹后序遍歷（145-中）
思路：
法1：反轉(zhuǎn)技巧：前序遍歷為 root -> left -> right，后序遍歷為 left -> right -> root卢肃∑Ｓ兀可以修改前序遍歷成為 root -> right -> left，那么這個(gè)順序就和后序遍歷正好相反莫湘。
法2：morris遍歷：二叉樹后序遍歷morris改寫(逆序打印右邊界)尤蒿。
1、對(duì)二叉樹遍歷中只出現(xiàn)一次的節(jié)點(diǎn)幅垮，即無左子樹的節(jié)點(diǎn)腰池，直接跳過
2、對(duì)于出現(xiàn)兩次的節(jié)點(diǎn)，第一次不管示弓，當(dāng)?shù)诙蔚竭_(dá)x的時(shí)候讳侨，逆序打印左子樹的右邊界
3、遍歷完成后奏属，打印整棵樹的右邊界
代碼：
// 1.反轉(zhuǎn)技巧
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) { //沒有到達(dá)左子樹的右邊界
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null; //第二次到達(dá)這個(gè)位置
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; //指向前一個(gè)節(jié)點(diǎn)（逆序）
}
reverseEdge(tail); //打印完成將原結(jié)構(gòu)還原（逆序回去）
}
//逆序右邊界
public static Node reverseEdge(Node from) { //逆序打印左子樹的右邊界,返回值是節(jié)點(diǎn)類型
Node pre = null;
Node next = null;
while (from != null) {
next = from.right;
from.right = pre; //改變指針的方向跨跨，指向前一個(gè)節(jié)點(diǎn)
pre = from; //記錄前一個(gè)節(jié)點(diǎn)
from = next; //from = from.right
}
return pre; //返回左子樹右邊界的最后一個(gè)元素
}
3.非遞歸進(jìn)行二叉樹中序遍歷（94-中）
思路：
法1：迭代：中序遍歷的順序是【左中右】。每到一個(gè)節(jié)點(diǎn)node拍皮，因?yàn)楦?jié)點(diǎn)的訪問在中間歹叮，先將node入棧。先遍歷左子樹铆帽，訪問node節(jié)點(diǎn)咆耿，最后訪問右子樹。訪問完node節(jié)點(diǎn)就可以出棧（已經(jīng)完成左子樹和node節(jié)點(diǎn)）爹橱。注：循環(huán)進(jìn)入條件包括棧非空萨螺。
法2：morris遍歷，記錄一個(gè)節(jié)點(diǎn)(出現(xiàn)多次)在morris序中第二次訪問的順序和只出現(xiàn)一次的節(jié)點(diǎn)愧驱，即左子樹的右邊界指向cur時(shí)慰技，我們第二次到達(dá)cur節(jié)點(diǎn)。
代碼：
// 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節(jié)點(diǎn)已經(jīng)完成
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情況组砚，繼續(xù)判斷cur的情況
} else {
mostRight.right = null;
}
}
ret.add(cur.val); //記錄只到達(dá)一次的點(diǎn)（無左孩子）和第二次到達(dá)curＮ巧獭！糟红！
cur = cur.right;
}
return ret;
}
