# 二叉樹的遍歷 # 二叉樹的遍歷算法 ## 概述 二叉樹作為一個基礎的數據結構，遍歷算法作為一個基礎的算法，兩者結合當然是經典的組合了。很多題目都會有 ta 的身影，有直接問二叉樹的遍歷的，有間接問的。比如要你找到樹中滿足條件的節點，就是間接考察樹的遍歷，因為你要找到樹中滿足條件的點，就需要進行遍歷。 > 你如果掌握了二叉樹的遍歷，那么也許其他復雜的樹對于你來說也并不遙遠了 二叉數的遍歷主要有前中后遍歷和層次遍歷。 前中后屬于 DFS，層次遍歷屬于 BFS。 DFS 和 BFS 都有著自己的應用，比如 leetcode 301 號問題和 609 號問題。 DFS 都可以使用棧來簡化操作，并且其實樹本身是一種遞歸的數據結構，因此遞歸和棧對于 DFS 來說是兩個關鍵點。 DFS 圖解：  (圖片來自 <https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search>) BFS 的關鍵點在于如何記錄每一層次是否遍歷完成， 我們可以用一個標識位來表式當前層的結束。 首先不管是前中還是后序遍歷，變的只是根節點的位置， 左右節點的順序永遠是先左后右。 比如前序遍歷就是根在前面，即根左右。中序就是根在中間，即左根右。后序就是根在后面，即左右根。 下面我們依次講解： ## 前序遍歷 相關問題[144.binary-tree-preorder-traversal](144.binary-tree-preorder-traversal.html) 前序遍歷的順序是`根-左-右` 思路是： 1. 先將根結點入棧 2. 出棧一個元素，將右節點和左節點依次入棧 3. 重復 2 的步驟 總結： 典型的遞歸數據結構，典型的用棧來簡化操作的算法。 其實從宏觀上表現為：`自頂向下依次訪問左側鏈，然后自底向上依次訪問右側鏈`， 如果從這個角度出發去寫的話，算法就不一樣了。從上向下我們可以直接遞歸訪問即可，從下向上我們只需要借助棧也可以輕易做到。 整個過程大概是這樣：  這種思路解題有點像我總結過的一個解題思路`backtrack` - 回溯法。這種思路有一個好處就是 可以`統一三種遍歷的思路`. 這個很重要，如果不了解的朋友，希望能夠記住這一點。 ## 中序遍歷 相關問題[94.binary-tree-inorder-traversal](94.binary-tree-inorder-traversal.html) 中序遍歷的順序是 `左-根-右`，根節點不是先輸出，這就有一點點復雜了。 1. 根節點入棧 2. 判斷有沒有左節點，如果有，則入棧，直到葉子節點 > 此時棧中保存的就是所有的左節點和根節點。 1. 出棧，判斷有沒有右節點，有則入棧，繼續執行 2 值得注意的是，中序遍歷一個二叉查找樹（BST）的結果是一個有序數組，利用這個性質有些題目可以得到簡化， 比如[230.kth-smallest-element-in-a-bst](230.kth-smallest-element-in-a-bst.html)， 以及[98.validate-binary-search-tree](98.validate-binary-search-tree.html) ## 后序遍歷 相關問題[145.binary-tree-postorder-traversal](145.binary-tree-postorder-traversal.html) 后序遍歷的順序是 `左-右-根` 這個就有點難度了，要不也不會是 leetcode 困難的 難度啊。 其實這個也是屬于根節點先不輸出，并且根節點是最后輸出。 這里可以采用一種討巧的做法， 就是記錄當前節點狀態，如果 1. 當前節點是葉子節點或者 2.當前節點的左右子樹都已經遍歷過了，那么就可以出棧了。 對于 1. 當前節點是葉子節點，這個比較好判斷，只要判斷 left 和 rigt 是否同時為 null 就好。 對于 2. 當前節點的左右子樹都已經遍歷過了， 我們只需要用一個變量記錄即可。最壞的情況，我們記錄每一個節點的訪問狀況就好了，空間復雜度 O(n) 但是仔細想一下，我們使用了棧的結構，從葉子節點開始輸出，我們記錄一個當前出棧的元素就好了，空間復雜度 O(1)， 具體請查看上方鏈接。 ## 層次遍歷 層次遍歷的關鍵點在于如何記錄每一層次是否遍歷完成， 我們可以用一個標識位來表式當前層的結束。  (圖片來自 <https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/breadth-first-search>) 具體做法： 1. 根節點入隊列， 并入隊列一個特殊的標識位，此處是 null 2. 出隊列 3. 判斷是不是 null， 如果是則代表本層已經結束。我們再次判斷是否當前隊列為空，如果不為空繼續入隊一個 null，否則說明遍歷已經完成，我們什么都不不用做 4. 如果不為 null，說明這一層還沒完，則將其左右子樹依次入隊列。 相關問題： - [102.binary-tree-level-order-traversal](102.binary-tree-level-order-traversal.html) - [117. 填充每個節點的下一個右側節點指針 II](https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/) ## 雙色標記法 我們知道垃圾回收算法中，有一種算法叫三色標記法。 即： - 用白色表示尚未訪問 - 灰色表示尚未完全訪問子節點 - 黑色表示子節點全部訪問 那么我們可以模仿其思想，使用雙色標記法來統一三種遍歷。 其核心思想如下： - 使用顏色標記節點的狀態，新節點為白色，已訪問的節點為灰色。 - 如果遇到的節點為白色，則將其標記為灰色，然后將其右子節點、自身、左子節點依次入棧。 - 如果遇到的節點為灰色，則將節點的值輸出。 使用這種方法實現的中序遍歷如下： ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">inorderTraversal</span><span class="hljs-params">(self, root: TreeNode)</span> -> List[int]:</span> WHITE, GRAY = <span class="hljs-params">0</span>, <span class="hljs-params">1</span> res = [] stack = [(WHITE, root)] <span class="hljs-keyword">while</span> stack: color, node = stack.pop() <span class="hljs-keyword">if</span> node <span class="hljs-keyword">is</span> <span class="hljs-keyword">None</span>: <span class="hljs-keyword">continue</span> <span class="hljs-keyword">if</span> color == WHITE: stack.append((WHITE, node.right)) stack.append((GRAY, node)) stack.append((WHITE, node.left)) <span class="hljs-keyword">else</span>: res.append(node.val) <span class="hljs-keyword">return</span> res ``` ``` 可以看出，實現上 WHITE 就表示的是遞歸中的第一次進入過程，Gray 則表示遞歸中的從葉子節點返回的過程。 因此這種迭代的寫法更接近遞歸寫法的本質。 如要實現前序、后序遍歷，只需要調整左右子節點的入棧順序即可。可以看出使用三色標記法， 其寫法類似遞歸的形式，因此便于記憶和書寫，缺點是使用了額外的內存空間。不過這個額外的空間是線性的，影響倒是不大。 > 雖然遞歸也是額外的線性時間，但是遞歸的棧開銷還是比一個 0，1 變量開銷大的。 ## Morris 遍歷 我們可以使用一種叫做 Morris 遍歷的方法，既不使用遞歸也不借助于棧。從而在 O(1)O(1)O(1) 空間完成這個過程。 ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">MorrisTraversal</span><span class="hljs-params">(root)</span>:</span> curr = root <span class="hljs-keyword">while</span> curr: <span class="hljs-title"># If left child is null, print the</span> <span class="hljs-title"># current node data. And, update</span> <span class="hljs-title"># the current pointer to right child.</span> <span class="hljs-keyword">if</span> curr.left <span class="hljs-keyword">is</span> <span class="hljs-keyword">None</span>: print(curr.data, end= <span class="hljs-string">" "</span>) curr = curr.right <span class="hljs-keyword">else</span>: <span class="hljs-title"># Find the inorder predecessor</span> prev = curr.left <span class="hljs-keyword">while</span> prev.right <span class="hljs-keyword">is</span> <span class="hljs-keyword">not</span> <span class="hljs-keyword">None</span> <span class="hljs-keyword">and</span> prev.right <span class="hljs-keyword">is</span> <span class="hljs-keyword">not</span> curr: prev = prev.right <span class="hljs-title"># If the right child of inorder</span> <span class="hljs-title"># predecessor already points to</span> <span class="hljs-title"># the current node, update the</span> <span class="hljs-title"># current with it's right child</span> <span class="hljs-keyword">if</span> prev.right <span class="hljs-keyword">is</span> curr: prev.right = <span class="hljs-keyword">None</span> curr = curr.right <span class="hljs-title"># else If right child doesn't point</span> <span class="hljs-title"># to the current node, then print this</span> <span class="hljs-title"># node's data and update the right child</span> <span class="hljs-title"># pointer with the current node and update</span> <span class="hljs-title"># the current with it's left child</span> <span class="hljs-keyword">else</span>: <span class="hljs-keyword">print</span> (curr.data, end=<span class="hljs-string">" "</span>) prev.right = curr curr = curr.left ``` ``` 參考： [what-is-morris-traversal](https://www.educative.io/edpresso/what-is-morris-traversal) ## 相關題目 - [lowest-common-ancestor-of-a-binary-tree](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/) - [binary-tree-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/) - [binary-tree-zigzag-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/) - [validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/) - [maximum-depth-of-binary-tree](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/) - [balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/) - [binary-tree-level-order-traversal-ii](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/) - [binary-tree-maximum-path-sum](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/) - [insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)