<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                # 二叉樹的遍歷 # 二叉樹的遍歷算法 ## 概述 二叉樹作為一個基礎的數據結構,遍歷算法作為一個基礎的算法,兩者結合當然是經典的組合了。很多題目都會有 ta 的身影,有直接問二叉樹的遍歷的,有間接問的。比如要你找到樹中滿足條件的節點,就是間接考察樹的遍歷,因為你要找到樹中滿足條件的點,就需要進行遍歷。 > 你如果掌握了二叉樹的遍歷,那么也許其他復雜的樹對于你來說也并不遙遠了 二叉數的遍歷主要有前中后遍歷和層次遍歷。 前中后屬于 DFS,層次遍歷屬于 BFS。 DFS 和 BFS 都有著自己的應用,比如 leetcode 301 號問題和 609 號問題。 DFS 都可以使用棧來簡化操作,并且其實樹本身是一種遞歸的數據結構,因此遞歸和棧對于 DFS 來說是兩個關鍵點。 DFS 圖解: ![](https://img.kancloud.cn/0b/83/0b83cd5ba24a3ebc4684dbde1823a2a4_500x500.gif) (圖片來自 <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 的步驟 總結: 典型的遞歸數據結構,典型的用棧來簡化操作的算法。 其實從宏觀上表現為:`自頂向下依次訪問左側鏈,然后自底向上依次訪問右側鏈`, 如果從這個角度出發去寫的話,算法就不一樣了。從上向下我們可以直接遞歸訪問即可,從下向上我們只需要借助棧也可以輕易做到。 整個過程大概是這樣: ![](https://img.kancloud.cn/59/09/5909e07ac17f816f484b3e4cfcf67791_831x395.jpg) 這種思路解題有點像我總結過的一個解題思路`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://img.kancloud.cn/04/e4/04e4086545c8693e292484da0ce590f0_500x500.gif) (圖片來自 <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/)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看