前言
二叉樹的遍歷可能大家都比較熟悉了往枣，這篇文章主要介紹了三種二叉樹的遍歷方法——遞歸伐庭、迭代和莫里斯遍歷，他們各自有各自的特點分冈。其中最重要的是莫里斯遍歷圾另，相對于前兩種方法比較少見，只需要固定的空間就可以完成迭代遍歷雕沉。這篇文章將會結合動圖集乔，帶你了解關于樹遍歷的知識。
簡介
我們通常希望通過訪問樹的每個節(jié)點來處理二叉樹，每次執(zhí)行特定的操作扰路，例如打印節(jié)點的內容尤溜、得到樹的所有節(jié)點的總和或者要找到最大的值。以某種順序訪問所有節(jié)點的過程稱為遍歷汗唱，僅遍歷樹中每個節(jié)點一次的遍歷稱為樹節(jié)點的枚舉宫莱。某些應用不需要以任何特定順序訪問節(jié)點，只要每個節(jié)點被精確訪問一次即可哩罪；有些應用授霸，必須按保留某些關系的順序訪問節(jié)點。
線性數(shù)據(jù)結構（如數(shù)組际插、堆棧碘耳、隊列和鏈表）只有一種讀取數(shù)據(jù)的方法，但是像樹這樣的分層數(shù)據(jù)結構可以以不同的方式遍歷框弛。
遍歷種類
根據(jù)我們遍歷樹的順序辛辨，我們把遍歷分成三種，分別是：
- 中序遍歷
- 前序遍歷
- 后序遍歷
這些遍歷方式和樹的結構有關瑟枫。
中序遍歷
- 先遍歷左子樹
- 再遍歷父節(jié)點
- 最后遍歷右子樹
圖片中的中序遍歷結果應該是[4,2,5,1,6,3,7]
前序遍歷
- 先遍歷父節(jié)點
- 再遍歷左子樹
- 最后遍歷右子樹
圖片中的前序遍歷結果應該是[1,2,4,5,3,6,7]
后序遍歷
- 先遍歷左子樹
- 再遍歷右子樹
- 最后遍歷父節(jié)點
圖中的后序遍歷結果應該是[4,5,2,6,7,3,1]
代碼實現(xiàn)
首先定義樹的結構
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
在代碼實現(xiàn)里面我們要返回按照特定遍歷順序依次遍歷的節(jié)點
中序實現(xiàn)
中序遞歸
按照中序遍歷的定義可以很容易用遞歸來實現(xiàn)
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>(); // 保存最后的結果
inorderTraversal(root, res);
return res;
}
public void inorderTraversal(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inorderTraversal(root.left, res); // 遍歷左子樹
res.add(root.val); // 遍歷父節(jié)點
inorderTraversal(root.right, res); // 遍歷右子樹
}
中序迭代
采用迭代的方法就有點復雜了斗搞，需要借助額外的數(shù)據(jù)結構——棧。
這個方法的思路是：
先從父結點遍歷左子節(jié)點力奋，一直遍歷到不再存在左子節(jié)點，然后從棧頂開始檢查幽七，對剛才遍歷的節(jié)點進行逆向遍歷景殷，找到每一個節(jié)點的右子節(jié)點，如果這些右子節(jié)點有左節(jié)點就繼續(xù)壓入棧中（相當于下次遍歷要從這個右子節(jié)點的左子樹開始）澡屡，繼續(xù)上面的過程猿挚。
整個相當于深度優(yōu)先遍歷，從每個節(jié)點的左節(jié)點遍歷驶鹉，遍歷父節(jié)點绩蜻，最后遍歷右節(jié)點。棧的作用相當于記住了上次遍歷的位置室埋，用來保存下次應該開始遍歷的節(jié)點办绝。
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
Stack<TreeNode> stack = new Stack<>();
List<Integer> res = new ArrayList<>(); // 遍歷結果
stack.push(root);
TreeNode cur = root.left;
while (!stack.isEmpty() || cur != null) {
while (cur != null) { // 先將所有的左節(jié)點的內容壓入棧中
stack.push(cur);
cur = cur.left;
}
cur = stack.pop(); // 出棧的時候進行遍歷
res.add(cur.val);
cur = cur.right; // 代表開始遍歷右子樹
}
return res;
}
中序莫里斯迭代
莫里斯遍歷不需要遞歸或者臨時的棧空間就可以完成遍歷姚淆，空間復雜度是常數(shù)孕蝉。但是為了解決從子節(jié)點找到父節(jié)點的問題，需要臨時修改樹的結構腌逢，在遍歷完成之后復原成原來的樹結構降淮。
整個遍歷的過程中只需要兩個指針——當前指針cur和臨時前驅指針prev，具體的過程如下
- 如果左子節(jié)點是空搏讶，錄入當前節(jié)點佳鳖，當前指針
cur指向右子節(jié)點 - 如果左子節(jié)點不是空霍殴，遍歷左子節(jié)點的最右側右子節(jié)點，找到最右側葉節(jié)點系吩，在尋找的過程中可能出現(xiàn)兩種情況：
- 如果遍歷到的葉節(jié)點的右子節(jié)點是空来庭，把葉節(jié)點的右子節(jié)點指向
cur節(jié)點，cur移向左子節(jié)點 - 如果遍歷到的葉節(jié)點的右子節(jié)點是
cur節(jié)點淑玫，表示原來的葉節(jié)點到cur節(jié)點連接已經存在巾腕，現(xiàn)在遍歷結束了，需要復原絮蒿，置節(jié)點的右子節(jié)點為空尊搬，在錄入了cur節(jié)點之后，cur移到自己的右子節(jié)點
- 如果遍歷到的葉節(jié)點的右子節(jié)點是空来庭，把葉節(jié)點的右子節(jié)點指向
- 重復上面兩步直到當前節(jié)點為空
其中最不好理解的是第二步土涝，遍歷左子樹的右節(jié)點的過程中佛寿，只有當左子樹沒有建立到父節(jié)點的連接的時候，才能最后遍歷到盡頭但壮，達到盡頭之后需要和父節(jié)點連接起來冀泻，當cur遍歷到這個葉節(jié)點的時候才能回到正確的父節(jié)點的位置。
當當前節(jié)點cur遍歷完了左子樹回到父節(jié)點的時候蜡饵，多余的連接還是存在的弹渔，需要移除這個連接，而方法就是和建立連接一樣遍歷左子樹找到最右側節(jié)點溯祸，這個時候判斷的依據(jù)就不能是右節(jié)點為空肢专，必須是左子節(jié)點的最右節(jié)點等于當前節(jié)點，相當于找到循環(huán)的起點焦辅，然后在這個地方切斷聯(lián)系博杖。
代碼實現(xiàn)：
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
TreeNode cur = root; // 記錄當前節(jié)點位置
List<Integer> res = new ArrayList<>();
while (cur != null) {
if (cur.left == null) { // 左節(jié)點為空，移到右子節(jié)點
res.add(cur.val);
cur = cur.right;
} else {
TreeNode prev = cur.left;
while (prev.right != null && prev.right != cur) { // 遍歷到左子樹的最右側節(jié)點
prev = prev.right;
}
if (prev.right == null) { // 建立返回父節(jié)點連接
prev.right = cur;
cur = cur.left;
} else { // 左子樹建立了連接筷登，說明遍歷完了剃根，可以拆除連接
res.add(cur.val); // 中序遍歷錄入當前節(jié)點
prev.right = null;
cur = cur.right;
}
}
}
return res;
}
時間復雜度分析：莫里斯遍歷的空間復雜度是常數(shù)狈醉，這個比較好理解惠险，但是時間復雜度為什么是O(n)呢莺匠？明明在代碼里面有個嵌套的循環(huán)可能會提高時間復雜度：
while (prev.right != null && prev.right != cur) { // 遍歷到左子樹的最右側節(jié)點
prev = prev.right;
}
可是如果在圖中模擬一下這個循環(huán)就會發(fā)現(xiàn)其實在尋找前驅節(jié)點的過程中，所有的節(jié)點其實最多只被遍歷了兩遍宵呛！比如對于節(jié)點1码秉，在尋找前驅節(jié)點的時候遍歷了2和5；當cur從5回到1之后，又遍歷了一遍2和5赡译，至此2和5在所有尋找前驅節(jié)點的過程中各遍歷了兩邊狂男，而在尋找2..7的前驅節(jié)點的時候舞吭，都沒有遍歷到2和5（除去了從2和5本身開始查找前驅節(jié)點時對自己的遍歷），所以2和5總體在前驅搜索的過程中只有兩次，加上他們自身的遍歷纵朋，也就只有3次聂薪。綜合來說肘交，樹的每個節(jié)點的遍歷次數(shù)最多都是3次复罐，所以時間復雜度是O(n)級別的乱投。
前序實現(xiàn)
前序遞歸
和中序的遞歸差不多施掏，只有一行代碼的區(qū)別：
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>(); // 保存最后的結果
preorderTraversal(root, res);
return res;
}
public void preorderTraversal(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val); // 遍歷父節(jié)點 注意這行代碼提前了
preorderTraversal(root.left, res); // 遍歷左子樹
preorderTraversal(root.right, res); // 遍歷右子樹
}
前序迭代
直接根據(jù)中序迭代的方法七芭，將記錄遍歷元素的時機改為了在入棧的時候就記錄，也就是將父節(jié)點計入數(shù)組的時間提前了预明。
public List<Integer> preorderTraversal3(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
Stack<TreeNode> stack = new Stack<>();
List<Integer> res = new ArrayList<>(); // 遍歷結果
stack.push(root);
TreeNode cur = root.left;
res.add(root.val); // 記錄根節(jié)點元素
while (!stack.isEmpty() || cur != null) {
while (cur != null) { // 先將所有的左節(jié)點的內容壓入棧中
stack.push(cur);
res.add(cur.val); // 這里在入棧的時候就要記錄遍歷的元素
cur = cur.left;
}
cur = stack.pop();
cur = cur.right; // 代表開始遍歷右子樹
}
return res;
}
前序莫里斯
和中序莫里斯遍歷的代碼也基本一樣究西，只不過當左子節(jié)點存在的時候，添加節(jié)點元素的位置從拆除多余連接的時候變成了建立連接的時候卓练，也就是在移動cur指針之前就得記錄節(jié)點隘蝎，保證當前指向的節(jié)點是最先記錄的，左右子樹的節(jié)點要靠后顽悼，并且不能重復記錄元素曼振。
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
TreeNode cur = root; // 記錄當前節(jié)點位置
List<Integer> res = new ArrayList<>();
while (cur != null) {
if (cur.left == null) { // 左節(jié)點為空，移到右子節(jié)點
res.add(cur.val);
cur = cur.right;
} else {
TreeNode prev = cur.left;
while (prev.right != null && prev.right != cur) { // 遍歷到左子樹的最右側節(jié)點
prev = prev.right;
}
if (prev.right == null) { // 建立返回父節(jié)點連接
prev.right = cur;
res.add(cur.val); // 注意添加元素到數(shù)組的代碼位置移到了這里
cur = cur.left;
} else { // 左子樹建立了連接蔚龙，說明遍歷完了冰评，可以拆除連接
prev.right = null;
cur = cur.right;
}
}
}
return res;
}
后序實現(xiàn)
后序遞歸
后序遞歸和前中遞歸的實現(xiàn)差不多，只需要把錄入元素的時機放在遍歷左右子樹之后就行了
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>(); // 保存最后的結果
postorderTraversal(root, res);
return res;
}
public void postorderTraversal(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
postorderTraversal(root.left, res); // 遍歷左子樹
postorderTraversal(root.right, res); // 遍歷右子樹
res.add(root.val); // 遍歷父節(jié)點
}
還有另外一種遞歸可能會對我們后序迭代算法略有啟發(fā)：我們可以通過將遍歷父節(jié)點操作放在最前面木羹，然后交換遍歷左右子樹的順序甲雅，得到反轉的后序遍歷結果，最后反轉一下就能得到正確的遍歷結果汇跨。
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>(); // 保存最后的結果
postorderTraversal(root, res);
Collections.reverse(res); // 反轉數(shù)組
return res;
}
public void postorderTraversal(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val); // 遍歷父節(jié)點
postorderTraversal(root.right, res); // 遍歷右子樹
postorderTraversal(root.left, res); // 遍歷左子樹
}
后序迭代
后序迭代就比較巧妙了务荆，利用上面講到的修改前序遍歷的遍歷左右子樹的順序妆距，移植到迭代過程中的棧的操作穷遂，把原來的所有的right改成left，原來的left改成right
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
Stack<TreeNode> stack = new Stack<>();
List<Integer> res = new ArrayList<>(); // 遍歷結果
stack.push(root);
TreeNode cur = root.right;
res.add(root.val); // 添加根節(jié)點娱据，反轉后變成最后元素
while (!stack.isEmpty() || cur != null) {
while (cur != null) { // 先將所有的右節(jié)點的內容壓入棧中
stack.push(cur);
res.add(cur.val); // 添加當前遍歷的節(jié)點
cur = cur.right;
}
cur = stack.pop();
cur = cur.left; // 代表開始遍歷左子樹
}
Collections.reverse(res); // 反轉最后的結果
return res;
}
后序莫里斯迭代
修改后序莫里斯迭代的思路其實和上面修改后序迭代的思路一樣
- 把前序莫里斯遍歷的代碼粘貼過來
- 把原來所有的
right改成left蚪黑，把原來所有的left改成right - 返回結果之前反轉一下數(shù)組
這種后序迭代遍歷的核心思路都是通過交換前序遍歷中遍歷左右子樹的順序盅惜，達到完全逆轉后序遍歷的結果，最后反轉得到正確的結果忌穿。
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
TreeNode cur = root; // 記錄當前節(jié)點位置
List<Integer> res = new ArrayList<>();
while (cur != null) {
if (cur.right == null) { // 右節(jié)點為空抒寂，移到左子節(jié)點
res.add(cur.val);
cur = cur.left;
} else {
TreeNode prev = cur.right;
while (prev.left != null && prev.left != cur) { // 遍歷右子樹的最左側節(jié)點
prev = prev.left;
}
if (prev.left == null) { // 建立返回父節(jié)點連接
prev.left = cur;
res.add(cur.val); // 添加元素到數(shù)組
cur = cur.right;
} else { // 右子樹建立了連接，說明遍歷完了掠剑，可以拆除連接
prev.left = null;
cur = cur.left;
}
}
}
Collections.reverse(res); // 最后要反轉數(shù)組得到最后的結果
return res;
}
總結
總的來說二叉樹的遍歷是非常重要也是非城撸基礎的知識，大部分人都能夠輕松的寫出遞歸的做法朴译，遞歸的代碼是最簡潔明了容易理解的井佑。
迭代的解決方法比較少見，需要額外的數(shù)據(jù)結構眠寿，循環(huán)的邏輯也不是那么容易理解躬翁，但是在面試或者OJ系統(tǒng)里面可能會出現(xiàn)的比較多。
關于莫里斯遍歷盯拱，可能大多數(shù)人都沒有聽說過這種巧妙的遍歷方法盒发，需要修改樹的結構以降低空間開銷，同時在遍歷結束之后還要復原樹的結構狡逢。這種遍歷相對于上面的迭代更加難以理解宁舰，但是它只需要兩個變量就可以完成遍歷的特點令人影響深刻。
參考
Morris Traversal方法遍歷二叉樹（非遞歸奢浑，不用棧明吩，O(1)空間）
What is Morris traversal?
二叉樹的前序、中序殷费、后序遍歷—迭代方法
更多精彩內容請看我的個人博客
