【演算法】二叉樹遍歷演算法總結：前序中序後序遍歷
- 2020 年 2 月 26 日
- 筆記
前言
二叉樹遍歷是非常經典的演算法題，也是二叉樹的一道基礎演算法題。
但是在平常的筆試面試中，其出現的頻率其實並不是特別的高，我推測是這種題目相對來說比較基礎，算是一個基礎知識點。
比如劍指offer中出現的後序遍歷題目，是給出一個數字序列，讓你判斷是不是平衡二叉樹後序遍歷序列，這樣出題的難度比直接讓你寫後序遍歷難很多。
但是，二叉樹遍歷容易嗎？在遞歸方法下，前中後序遍歷都是一個思路，理解起來也比較容易。
但是只是用迭代的話，二叉樹遍歷其實是有難度的！，這也是為什麼LeetCode會在這三題題目的下方寫出進階: 遞歸演算法很簡單，你可以通過迭代演算法完成嗎？這句話了。
本文的主要內容如下：
- 題目定義：
- 上篇：二叉樹前序、中序、後序遍歷
- 下篇：層序遍歷、其他遍歷相關題型
- 解題思路：遞歸 + 迭代+ 莫里斯Morris遍歷
- 解題程式碼：Java + Python
注1：本文中的解題思路會盡量的全面，但是解題方法千變萬化，有很多奇技淫巧我不會去介紹，大家有興趣可以自行擴展學習。
注2：本文中的程式碼會盡量簡單，易懂，並不會去追求極致的寫法（比如：在一行內完成，使用各種非正式的庫等）。
正文
二叉樹的定義
最多有兩棵子樹的樹被稱為二叉樹
二叉樹下還有很多種特殊的二叉樹，下方簡單介紹幾種常用的。
滿二叉樹
二叉樹中所有非葉子結點的度都是2，且葉子結點都在同一層次上
完全二叉樹（可以不滿）
如果一個二叉樹與滿二叉樹前m個節點的結構相同，這樣的二叉樹被稱為完全二叉樹。也就是說，如果把滿二叉樹從右至左、從下往上刪除一些節點，剩餘的結構就構成完全二叉樹。
二叉搜索樹
二叉查找樹（BinarySearch Tree，也叫二叉搜索樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或者是具有下列性質的二叉樹：
- 若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
- 若它的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
- 它的左、右子樹也分別為二叉排序樹
二叉樹前中後序遍歷
遍歷方法
前序遍歷：根結點 —> 左子樹 —> 右子樹
中序遍歷：左子樹—> 根結點 —> 右子樹
後序遍歷：左子樹 —> 右子樹 —> 根結點
題目介紹
前序遍歷
LeetCode題目地址：
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
輸入: [1,null,2,3] 1 2 / 3 輸出: [1,2,3]
中序遍歷
LeetCode題目地址：
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
輸入: [1,null,2,3] 1 2 / 3 輸出: [1,3,2]
後序遍歷
LeetCode題目地址：
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
輸入: [1,null,2,3] 1 2 / 3 輸出: [3,2,1]
解題思路詳解與程式碼實現
二叉樹的前中後序遍歷，主要就是兩種思路，一種是遞歸，一種是迭代。
如果看到這裡還沒有感覺，不用擔心，先直接往下看，第一個程式碼（前序遍歷的遞歸思路）會幫助你提升感覺。
遞歸思路
遞歸思路是最容易理解的思路，並且前中後序遍歷都相同。
比如前序遍歷，在遞歸的函數里，先往結果數組裡加入根節點，然後加入根節點的左節點，然後加入根節點的右節點。最後所有遞歸的函數運行完畢，結果集就已經完成了。
中序和後序的思路相同，就不再贅述了。
前序遍歷
Java：
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } preorder(root, result); return result; } private static List<Integer> preorder(TreeNode root, List<Integer> result) { if (root != null) { result.add(root.val); preorder(root.left, result); preorder(root.right, result); } return result; } }
Python：
class Solution(object): def _preorderTraversal(self, root, result): if root: result.append(root.val) self._preorderTraversal(root.left, result) self._preorderTraversal(root.right, result) def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root == None: return [] result = [] self._preorderTraversal(root, result) return result
中序遍歷
Java：
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } result = inorder(root, result); return result; } private static List<Integer> inorder(TreeNode root, List<Integer> result) { if (root != null) { inorder(root.left, result); result.add(root.val); inorder(root.right, result); } return result; } }
Python：
class Solution(object): def generate(self, root, result): if root: self.inorder(root.left, list) result.append(root.val) self.inorder(root.right, list) def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return [] result = [] self.generate(root, result) return result
後序遍歷
Java：
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } result = postorder(root, result); return result; } private static List<Integer> postorder(TreeNode root, List<Integer> result) { if (root != null) { postorder(root.left, result); postorder(root.right, result); result.add(root.val); } return result; } }
Python：
class Solution(object): def _postorderTraversal(self, root, result): if root: self._postorderTraversal(root.left, result) self._postorderTraversal(root.right, result) result.append(root.val) def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root == None: return [] result = [] self._postorderTraversal(root, result) return result
迭代思路
前序遍歷
我們需要一個棧來完成遍歷。
1.根節點入棧 2.取出節點，值加入結果，然後先加右，後加左。 3.重複2
這樣就得到了 根節點——左子樹——右子樹 的遍歷結果集。
Java：
來自官方題解
LinkedList<TreeNode> stack = new LinkedList<>(); LinkedList<Integer> output = new LinkedList<>(); if (root == null) { return output; } stack.add(root); while (!stack.isEmpty()) { TreeNode node = stack.pollLast(); output.add(node.val); if (node.right != null) { stack.add(node.right); } if (node.left != null) { stack.add(node.left); } } return output; }
Python：
class Solution(object): def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ ret = [] stack = [root] while stack: node = stack.pop() if node: ret.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return ret
中序遍歷
還是使用一個棧來解決問題。
步驟如下：
1 / 2 3 / / 4 5 6 7
- 我們將根節點1入棧，如果有左孩子，依次入棧，那麼入棧順序為：1，2，4。由於4的左子樹為空，停止入棧，此時棧為{1，2，4}。
- 此時將4出棧，並遍歷4，由於4也沒有右孩子，那麼根據中序遍歷的規則，我們顯然應該繼續遍歷4的父親2，情況是這樣。所以我們繼續將2出棧並遍歷2，2存在右孩子，將5入棧，此時棧為{1，5}。
- 5沒有孩子，則將5出棧並遍歷5，這也符合中序遍歷的規則。此時棧為{1}。
- 1有右孩子，則將1出棧並遍歷1，然後將右孩子3入棧，並繼續以上三個步驟即可。
棧的變化過程：{1}->{1,2}->{1,2,4}->{1,2}->{1}->{1,5}->{1}->{}->{3}->{3,6}->{3}->{}->{7}->{}。
總結：從根節點遍歷，先放入所有有左孩子的節點直到沒有，然後出棧，出棧的時候就將出棧的數字放入結果集，然後看其有沒有右孩子，有的話右孩子入棧。
Java：
官方題解
public class Solution { public List <Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); res.add(curr.val); curr = curr.right; } return res; } }
Python：
class Solution: # @param root, a tree node # @return a list of integers def inorderTraversal(self, root): result = [] stack = [] while root or stack: if root: stack.append(root) root = root.left else: root = stack.pop() result.append(root.val) root = root.right return result
後序遍歷
將數組輸出為右子樹-左子樹-根節點。最後，再將數組倒序輸出，形成後序遍歷。這樣程式碼並不用很繁瑣，也能做完迭代。
是不是似曾相識，沒錯，和前序遍歷的迭代幾乎一樣，僅僅是先放右節點再放左節點變成了先放左節點再放右節點，然後倒序輸出。
Java：
class Solution { public List<Integer> postorderTraversal(TreeNode root) { LinkedList<TreeNode> stack = new LinkedList<>(); LinkedList<Integer> output = new LinkedList<>(); if (root == null) { return output; } stack.add(root); while (!stack.isEmpty()) { TreeNode node = stack.pollLast(); output.addFirst(node.val); if (node.left != null) { stack.add(node.left); } if (node.right != null) { stack.add(node.right); } } return output; } }
Python：
class Solution(object): def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] ret = [] stack = [root] while stack: node = stack.pop() if node: ret.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return ret[::-1]
所以迭代方式，前後序是非常類似的，中序遍歷可能需要單獨理解下。
莫里斯遍歷
二叉樹常規的遍歷方法是用遞歸來實現的，這種方法一般都需要O(n)的空間複雜度和O(n)的時間複雜度。而Morris方法實現的是O(1)的空間複雜度和O(n)的時間複雜度。 我們知道，遍歷二叉樹時，最大的難點在於，遍歷到子節點的時候怎樣重新返回到父節點（假設節點中沒有指向父節點的p指針），由於不能用棧作為輔助空間。(不然就是普通迭代方法)。
為了解決這個問題，Morris方法用到了線索二叉樹（threaded binary tree）的概念。在Morris方法中不需要為每個節點額外分配指針指向其前驅（predecessor）和後繼節點（successor），只需要利用葉子節點中的左右空指針指向某種順序遍歷下的前驅節點或後繼節點就可以了。
聽不懂沒關係，下面使用中序遍歷作為例子來理解莫里斯遍歷到底是什麼意思，例子來自LeetCode官方題解：
中序遍歷
Step 1: 將當前節點current初始化為根節點 Step 2: While current不為空， 若current沒有左子節點 a. 將current添加到輸出 b. 進入右子樹，亦即, current = current.right 否則 a. 在current的左子樹中，令current成為最右側節點的右子節點 b. 進入左子樹，亦即，current = current.left
1 / 2 3 / / 4 5 6
首先，1 是根節點，所以將 current 初始化為 1。1 有左子節點 2，current 的左子樹是
2 / 4 5
在此左子樹中最右側的節點是 5，於是將 current(1) 作為 5 的右子節點。令 current = cuurent.left (current = 2)。現在二叉樹的形狀為:
2 / 4 5 1 3 / 6
對於 current(2)，其左子節點為4，我們可以繼續上述過程
4 2 5 1 3 / 6
Java：
class Solution { public List < Integer > inorderTraversal(TreeNode root) { List < Integer > res = new ArrayList < > (); TreeNode curr = root; TreeNode pre; while (curr != null) { if (curr.left == null) { res.add(curr.val); curr = curr.right; // move to next right node } else { // has a left subtree pre = curr.left; while (pre.right != null) { // find rightmost pre = pre.right; } pre.right = curr; // put cur after the pre node TreeNode temp = curr; // store cur node curr = curr.left; // move cur to the top of the new tree temp.left = null; // original cur left be null, avoid infinite loops } } return res; } }
前序遍歷
理解了中序遍歷，前序和後序遍歷相對來說也就更容易理解了。所以前序和後序貼了思路，程式碼我也沒自己寫後submit，在這裡就不放了。
演算法的思路是從當前節點向下訪問先序遍歷的前驅節點，每個前驅節點都恰好被訪問兩次。 首先從當前節點開始，向左孩子走一步然後沿著右孩子一直向下訪問，直到到達一個葉子節點（當前節點的中序遍歷前驅節點），所以我們更新輸出並建立一條偽邊 predecessor.right = root 更新這個前驅的下一個點。如果我們第二次訪問到前驅節點，由於已經指向了當前節點，我們移除偽邊並移動到下一個頂點。
後序遍歷
後續遍歷稍顯複雜，需要建立一個臨時節點dump，令其左孩子是root。並且還需要一個子過程，就是倒序輸出某兩個節點之間路徑上的各個節點。 步驟： 當前節點設置為臨時節點dump。
- 如果當前節點的左孩子為空，則將其右孩子作為當前節點。
- 如果當前節點的左孩子不為空，在當前節點的左子樹中找到當前節點在中序遍歷下的前驅節點。 a) 如果前驅節點的右孩子為空，將它的右孩子設置為當前節點。當前節點更新為當前節點的左孩子。 b) 如果前驅節點的右孩子為當前節點，將它的右孩子重新設為空。倒序輸出從當前節點的左孩子到該前驅節點這條路徑上的所有節點。當前節點更新為當前節點的右孩子。
- 重複以上1、2直到當前節點為空。
參考
- https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
- https://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html
- https://blog.csdn.net/softwarex4/article/details/95986102
關注我
我是一名後端開發工程師。
主要關注後端開發，數據安全，爬蟲，物聯網，邊緣計算等方向，歡迎交流。
各大平台都可以找到我
- 微信公眾號：後端技術漫談
- Github：@qqxx6661
- CSDN：@Rude3knife
- 知乎：@後端技術漫談
- 簡書：@蠻三刀把刀
- 掘金：@蠻三刀把刀
原創部落格主要內容
- 後端開發相關技術文章
- Java面試知識點複習全手冊
- 設計模式/數據結構
- LeetCode/劍指offer 演算法題解析
- SpringBoot/SpringCloud菜鳥入門實戰系列
- 爬蟲相關技術文章
- 逸聞趣事/好書分享/個人生活
