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

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0102. 二叉樹的層序遍歷 ## 題目地址(102. 二叉樹的層序遍歷) <https://leetcode-cn.com/problems/binary-tree-level-order-traversal/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個二叉樹,請你返回其按 層序遍歷 得到的節點值。 (即逐層地,從左到右訪問所有節點)。 示例: 二叉樹:[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其層次遍歷結果: [ [3], [9,20], [15,7] ] ``` ``` ## 前置知識 - 隊列 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這是一個典型的二叉樹遍歷問題, 關于二叉樹遍歷,我總結了一個[專題](https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-tree-traversal.md),大家可以先去看下那個,然后再來刷這道題。 這道題可以借助`隊列`實現,首先把root入隊,然后入隊一個特殊元素Null(來表示每層的結束)。 然后就是while(queue.length), 每次處理一個節點,都將其子節點(在這里是left和right)放到隊列中。 然后不斷的出隊, 如果出隊的是null,則表式這一層已經結束了,我們就繼續push一個null。 如果不入隊特殊元素Null來表示每層的結束,則在while循環開始時保存當前隊列的長度,以保證每次只遍歷一層(參考下面的C++ Code)。 > 如果采用遞歸方式,則需要將當前節點,當前所在的level以及結果數組傳遞給遞歸函數。在遞歸函數中,取出節點的值,添加到level參數對應結果數組元素中(參考下面的C++ Code 或 Python Code)。 ## 關鍵點解析 - 隊列 - 隊列中用Null(一個特殊元素)來劃分每層 - 樹的基本操作- 遍歷 - 層次遍歷(BFS) - 注意塞入null的時候,判斷一下當前隊列是否為空,不然會無限循環 ## 代碼 - 語言支持:JS,C++,Python3 Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {TreeNode} root * @return {number[][]} */</span> <span class="hljs-keyword">var</span> levelOrder = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">root</span>) </span>{ <span class="hljs-keyword">if</span> (!root) <span class="hljs-keyword">return</span> []; <span class="hljs-keyword">const</span> items = []; <span class="hljs-title">// 存放所有節點</span> <span class="hljs-keyword">const</span> queue = [root, <span class="hljs-params">null</span>]; <span class="hljs-title">// null 簡化操作</span> <span class="hljs-keyword">let</span> levelNodes = []; <span class="hljs-title">// 存放每一層的節點</span> <span class="hljs-keyword">while</span> (queue.length > <span class="hljs-params">0</span>) { <span class="hljs-keyword">const</span> t = queue.shift(); <span class="hljs-keyword">if</span> (t) { levelNodes.push(t.val) <span class="hljs-keyword">if</span> (t.left) { queue.push(t.left); } <span class="hljs-keyword">if</span> (t.right) { queue.push(t.right); } } <span class="hljs-keyword">else</span> { <span class="hljs-title">// 一層已經遍歷完了</span> items.push(levelNodes); levelNodes = []; <span class="hljs-keyword">if</span> (queue.length > <span class="hljs-params">0</span>) { queue.push(<span class="hljs-params">null</span>) } } } <span class="hljs-keyword">return</span> items; }; ``` ``` 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-title">// 迭代</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-params">vector</span><<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>> levelOrder(TreeNode* root) { <span class="hljs-keyword">auto</span> ret = <span class="hljs-params">vector</span><<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>>(); <span class="hljs-keyword">if</span> (root == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> ret; <span class="hljs-keyword">auto</span> q = <span class="hljs-params">vector</span><TreeNode*>(); q.push_back(root); <span class="hljs-keyword">auto</span> level = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (!q.empty()) { <span class="hljs-keyword">auto</span> sz = q.size(); ret.push_back(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>()); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> i = <span class="hljs-params">0</span>; i < sz; ++i) { <span class="hljs-keyword">auto</span> t = q.front(); q.erase(q.begin()); ret[level].push_back(t->val); <span class="hljs-keyword">if</span> (t->left != <span class="hljs-params">nullptr</span>) q.push_back(t->left); <span class="hljs-keyword">if</span> (t->right != <span class="hljs-params">nullptr</span>) q.push_back(t->right); } ++level; } <span class="hljs-keyword">return</span> ret; } }; <span class="hljs-title">// 遞歸</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-params">vector</span><<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>> levelOrder(TreeNode* root) { <span class="hljs-params">vector</span><<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>> v; levelOrder(root, <span class="hljs-params">0</span>, v); <span class="hljs-keyword">return</span> v; } <span class="hljs-keyword">private</span>: <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">levelOrder</span><span class="hljs-params">(TreeNode* root, <span class="hljs-keyword">int</span> level, <span class="hljs-params">vector</span><<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>>& v)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-params">NULL</span>) <span class="hljs-keyword">return</span>; <span class="hljs-keyword">if</span> (v.size() < level + <span class="hljs-params">1</span>) v.resize(level + <span class="hljs-params">1</span>); v[level].push_back(root->val); levelOrder(root->left, level + <span class="hljs-params">1</span>, v); levelOrder(root->right, level + <span class="hljs-params">1</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">levelOrder</span><span class="hljs-params">(self, root: TreeNode)</span> -> List[List[int]]:</span> <span class="hljs-string">"""遞歸法"""</span> <span class="hljs-keyword">if</span> root <span class="hljs-keyword">is</span> <span class="hljs-keyword">None</span>: <span class="hljs-keyword">return</span> [] result = [] <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">add_to_result</span><span class="hljs-params">(level, node)</span>:</span> <span class="hljs-string">"""遞歸函數 :param level int 當前在二叉樹的層次 :param node TreeNode 當前節點 """</span> <span class="hljs-keyword">if</span> level > len(result) - <span class="hljs-params">1</span>: result.append([]) result[level].append(node.val) <span class="hljs-keyword">if</span> node.left: add_to_result(level+<span class="hljs-params">1</span>, node.left) <span class="hljs-keyword">if</span> node.right: add_to_result(level+<span class="hljs-params">1</span>, node.right) add_to_result(<span class="hljs-params">0</span>, root) <span class="hljs-keyword">return</span> result ``` ``` ***復雜度分析*** - 時間復雜度:O(N)O(N)O(N),其中N為樹中節點總數。 - 空間復雜度:O(N)O(N)O(N),其中N為樹中節點總數。 更多題解可以訪問我的LeetCode題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經30K star啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ## 擴展 實際上這道題方法很多, 比如經典的三色標記法。 ## 相關題目 - [103.binary-tree-zigzag-level-order-traversal](103.binary-tree-zigzag-level-order-traversal.html) - [104.maximum-depth-of-binary-tree](104.maximum-depth-of-binary-tree.html) ## 相關專題 - [二叉樹的遍歷](https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-tree-traversal.md)
                  <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>

                              哎呀哎呀视频在线观看