<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>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 0145. 二叉樹的后序遍歷 ## 題目地址(145. 二叉樹的后序遍歷) <https://leetcode-cn.com/problems/binary-tree-postorder-traversal/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二叉樹,返回它的 后序 遍歷。 示例: 輸入: [1,null,2,3] 1 \ 2 / 3 輸出: [3,2,1] 進階: 遞歸算法很簡單,你可以通過迭代算法完成嗎? ``` ``` ## 前置知識 - 棧 - 遞歸 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 相比于前序遍歷,后續遍歷思維上難度要大些,前序遍歷是通過一個stack,首先壓入父親結點,然后彈出父親結點,并輸出它的value,之后壓人其右兒子,左兒子即可。 然而后序遍歷結點的訪問順序是:左兒子 -> 右兒子 -> 自己。那么一個結點需要兩種情況下才能夠輸出: 第一,它已經是葉子結點; 第二,它不是葉子結點,但是它的兒子已經輸出過。 那么基于此我們只需要記錄一下當前輸出的結點即可。對于一個新的結點,如果它不是葉子結點,兒子也沒有訪問,那么就需要將它的右兒子,左兒子壓入。 如果它滿足輸出條件,則輸出它,并記錄下當前輸出結點。輸出在stack為空時結束。 ## 關鍵點解析 - 二叉樹的基本操作(遍歷)> 不同的遍歷算法差異還是蠻大的 - 如果非遞歸的話利用棧來簡化操作 - 如果數據規模不大的話,建議使用遞歸 - 遞歸的問題需要注意兩點,一個是終止條件,一個如何縮小規模 - 終止條件,自然是當前這個元素是null(鏈表也是一樣) - 由于二叉樹本身就是一個遞歸結構, 每次處理一個子樹其實就是縮小了規模, 難點在于如何合并結果,這里的合并結果其實就是`left.concat(right).concat(mid)`, mid是一個具體的節點,left和right`遞歸求出即可` ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */</span> <span class="hljs-title">/** * @param {TreeNode} root * @return {number[]} */</span> <span class="hljs-keyword">var</span> postorderTraversal = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">root</span>) </span>{ <span class="hljs-title">// 1. Recursive solution</span> <span class="hljs-title">// if (!root) return [];</span> <span class="hljs-title">// return postorderTraversal(root.left).concat(postorderTraversal(root.right)).concat(root.val);</span> <span class="hljs-title">// 2. iterative solutuon</span> <span class="hljs-keyword">if</span> (!root) <span class="hljs-keyword">return</span> []; <span class="hljs-keyword">const</span> ret = []; <span class="hljs-keyword">const</span> stack = [root]; <span class="hljs-keyword">let</span> p = root; <span class="hljs-title">// 標識元素,用來判斷節點是否應該出棧</span> <span class="hljs-keyword">while</span> (stack.length > <span class="hljs-params">0</span>) { <span class="hljs-keyword">const</span> top = stack[stack.length - <span class="hljs-params">1</span>]; <span class="hljs-keyword">if</span> ( top.left === p || top.right === p || <span class="hljs-title">// 子節點已經遍歷過了</span> (top.left === <span class="hljs-params">null</span> && top.right === <span class="hljs-params">null</span>) <span class="hljs-title">// 葉子元素</span> ) { p = stack.pop(); ret.push(p.val); } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">if</span> (top.right) { stack.push(top.right); } <span class="hljs-keyword">if</span> (top.left) { stack.push(top.left); } } } <span class="hljs-keyword">return</span> ret; }; ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) ## 相關專題 - [二叉樹的遍歷](https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-tree-traversal.md) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <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>

                              哎呀哎呀视频在线观看