<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國際加速解決方案。 廣告
                # 0094. 二叉樹的中序遍歷 ## 題目地址(94. 二叉樹的中序遍歷) <https://leetcode-cn.com/problems/binary-tree-inorder-traversal/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二叉樹,返回它的中序 遍歷。 示例: 輸入: [1,null,2,3] 1 \ 2 / 3 輸出: [1,3,2] 進階: 遞歸算法很簡單,你可以通過迭代算法完成嗎? ``` ``` ## 前置知識 - 二叉樹 - 遞歸 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 遞歸的方式相對簡單,非遞歸的方式借助棧這種數據結構實現起來會相對輕松。 如果采用非遞歸,可以用棧(Stack)的思路來處理問題。 中序遍歷的順序為左-根-右,具體算法為: - 從根節點開始,先將根節點壓入棧 - 然后再將其所有左子結點壓入棧,取出棧頂節點,保存節點值 - 再將當前指針移到其右子節點上,若存在右子節點,則在下次循環時又可將其所有左子結點壓入棧中, 重復上步驟 ![](https://img.kancloud.cn/82/8c/828c1b13297bacd4c2b9276485b170d4_961x538.gif) (圖片來自: <https://github.com/MisterBooo/LeetCodeAnimation>) ## 關鍵點解析 - 二叉樹的基本操作(遍歷)> 不同的遍歷算法差異還是蠻大的 - 如果非遞歸的話利用棧來簡化操作 - 如果數據規模不大的話,建議使用遞歸 - 遞歸的問題需要注意兩點,一個是終止條件,一個如何縮小規模 - 終止條件,自然是當前這個元素是 null(鏈表也是一樣) - 由于二叉樹本身就是一個遞歸結構, 每次處理一個子樹其實就是縮小了規模, 難點在于如何合并結果,這里的合并結果其實就是`left.concat(mid).concat(right)`, mid 是一個具體的節點,left 和 right`遞歸求出即可` ## 代碼 - 語言支持:JS,C++,Python3, Java JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {TreeNode} root * @return {number[]} */</span> <span class="hljs-keyword">var</span> inorderTraversal = <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">// const left = root.left ? inorderTraversal(root.left) : [];</span> <span class="hljs-title">// const right = root.right ? inorderTraversal(root.right) : [];</span> <span class="hljs-title">// return left.concat([root.val]).concat(right);</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> stack = [root]; <span class="hljs-keyword">const</span> ret = []; <span class="hljs-keyword">let</span> left = root.left; <span class="hljs-keyword">let</span> item = <span class="hljs-params">null</span>; <span class="hljs-title">// stack 中彈出的當前項</span> <span class="hljs-keyword">while</span> (left) { stack.push(left); left = left.left; } <span class="hljs-keyword">while</span> ((item = stack.pop())) { ret.push(item.val); <span class="hljs-keyword">let</span> t = item.right; <span class="hljs-keyword">while</span> (t) { stack.push(t); t = t.left; } } <span class="hljs-keyword">return</span> ret; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>> inorderTraversal(TreeNode* root) { <span class="hljs-params">vector</span><TreeNode*> s; <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>> v; <span class="hljs-keyword">while</span> (root != <span class="hljs-params">NULL</span> || !s.empty()) { <span class="hljs-keyword">for</span> (; root != <span class="hljs-params">NULL</span>; root = root->left) s.push_back(root); v.push_back(s.back()->val); root = s.back()->right; s.pop_back(); } <span class="hljs-keyword">return</span> v; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># Definition for a binary tree node.</span> <span class="hljs-title"># class TreeNode:</span> <span class="hljs-title"># def __init__(self, x):</span> <span class="hljs-title"># self.val = x</span> <span class="hljs-title"># self.left = None</span> <span class="hljs-title"># self.right = None</span> <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> <span class="hljs-string">""" 1. 遞歸法可以一行代碼完成,無需討論; 2. 迭代法一般需要通過一個棧保存節點順序,我們這里直接使用列表 - 首先,我要按照中序遍歷的順序存入棧,這邊用的逆序,方便從尾部開始處理 - 在存入棧時加入一個是否需要深化的參數 - 在回頭取值時,這個參數應該是否,即直接取值 - 簡單調整順序,即可實現前序和后序遍歷 """</span> <span class="hljs-title"># 遞歸法</span> <span class="hljs-title"># if root is None:</span> <span class="hljs-title"># return []</span> <span class="hljs-title"># return self.inorderTraversal(root.left)\</span> <span class="hljs-title"># + [root.val]\</span> <span class="hljs-title"># + self.inorderTraversal(root.right)</span> <span class="hljs-title"># 迭代法</span> result = [] stack = [(<span class="hljs-params">1</span>, root)] <span class="hljs-keyword">while</span> stack: go_deeper, 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> go_deeper: <span class="hljs-title"># 左右節點還需繼續深化,并且入棧是先右后左</span> stack.append((<span class="hljs-params">1</span>, node.right)) <span class="hljs-title"># 節點自身已遍歷,回頭可以直接取值</span> stack.append((<span class="hljs-params">0</span>, node)) stack.append((<span class="hljs-params">1</span>, node.left)) <span class="hljs-keyword">else</span>: result.append(node.val) <span class="hljs-keyword">return</span> result ``` ``` Java Code: - recursion ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ List<Integer> res = <span class="hljs-keyword">new</span> LinkedList<>(); <span class="hljs-function"><span class="hljs-keyword">public</span> List<Integer> <span class="hljs-title">inorderTraversal</span><span class="hljs-params">(TreeNode root)</span> </span>{ inorder(root); <span class="hljs-keyword">return</span> res; } <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">inorder</span> <span class="hljs-params">(TreeNode root)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-keyword">null</span>) <span class="hljs-keyword">return</span>; inorder(root.left); res.add(root.val); inorder(root.right); } } ``` ``` - iteration ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */</span> <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">public</span> List<Integer> <span class="hljs-title">inorderTraversal</span><span class="hljs-params">(TreeNode root)</span> </span>{ List<Integer> res = <span class="hljs-keyword">new</span> ArrayList<> (); Stack<TreeNode> stack = <span class="hljs-keyword">new</span> Stack<> (); <span class="hljs-keyword">while</span> (root != <span class="hljs-keyword">null</span> || !stack.isEmpty()) { <span class="hljs-keyword">while</span> (root != <span class="hljs-keyword">null</span>) { stack.push(root); root = root.left; } root = stack.pop(); res.add(root.val); root = root.right; } <span class="hljs-keyword">return</span> res; } } ``` ``` ## 相關專題 - [二叉樹的遍歷](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>

                              哎呀哎呀视频在线观看