# 0103. 二叉樹的鋸齒形層次遍歷 ## 題目地址(103. 二叉樹的鋸齒形層次遍歷) <https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/> ## 題目描述 和leetcode 102 基本是一樣的，思路是完全一樣的。 ``` <pre class="calibre18">``` 給定一個二叉樹，返回其節點值的鋸齒形層次遍歷。（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行）。 例如： 給定二叉樹 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回鋸齒形層次遍歷如下： [ [3], [20,9], [15,7] ] ``` ``` ## 前置知識 - 隊列 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題可以借助`隊列`實現，首先把root入隊，然后入隊一個特殊元素Null(來表示每層的結束)。 然后就是while(queue.length), 每次處理一個節點，都將其子節點（在這里是left和right）放到隊列中。 然后不斷的出隊， 如果出隊的是null，則表式這一層已經結束了，我們就繼續push一個null。 ## 關鍵點解析 - 隊列 - 隊列中用Null(一個特殊元素)來劃分每層 - 樹的基本操作- 遍歷 - 層次遍歷（BFS） ## 代碼 - 語言支持：JS，C++ JavaScript Code： ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {TreeNode} root * @return {number[][]} */</span> <span class="hljs-keyword">var</span> zigzagLevelOrder = <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-keyword">let</span> isOdd = <span class="hljs-params">true</span>; <span class="hljs-keyword">let</span> levelNodes = []; <span class="hljs-keyword">const</span> queue = [root, <span class="hljs-params">null</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-keyword">if</span> (!isOdd) { levelNodes = levelNodes.reverse(); } items.push(levelNodes) levelNodes = []; isOdd = !isOdd; <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-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>>> zigzagLevelOrder(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> <span class="hljs-params">queue</span> = <span class="hljs-params">vector</span><<span class="hljs-keyword">const</span> TreeNode*>{root}; <span class="hljs-keyword">auto</span> isOdd = <span class="hljs-params">true</span>; <span class="hljs-keyword">while</span> (!<span class="hljs-params">queue</span>.empty()) { <span class="hljs-keyword">auto</span> sz = <span class="hljs-params">queue</span>.size(); <span class="hljs-keyword">auto</span> level = <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> n = <span class="hljs-params">queue</span>.front(); <span class="hljs-params">queue</span>.erase(<span class="hljs-params">queue</span>.begin()); <span class="hljs-keyword">if</span> (isOdd) level.push_back(n->val); <span class="hljs-keyword">else</span> level.insert(level.begin(), n->val); <span class="hljs-keyword">if</span> (n->left != <span class="hljs-params">nullptr</span>) <span class="hljs-params">queue</span>.push_back(n->left); <span class="hljs-keyword">if</span> (n->right != <span class="hljs-params">nullptr</span>) <span class="hljs-params">queue</span>.push_back(n->right); } isOdd = !isOdd; ret.push_back(level); } <span class="hljs-keyword">return</span> ret; } }; ``` ``` ## 拓展 由于二叉樹是遞歸結構，因此，可以采用遞歸的方式來處理。在遞歸時需要保留當前的層次信息（從0開始），作為參數傳遞給下一次遞歸調用。 ### 描述 1. 當前層次為偶數時，將當前節點放到當前層的結果數組尾部 2. 當前層次為奇數時，將當前節點放到當前層的結果數組頭部 3. 遞歸對左子樹進行之字形遍歷，層數參數為當前層數+1 4. 遞歸對右子樹進行之字形遍歷，層數參數為當前層數+1 ### C++實現 ``` <pre class="calibre18">``` <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>>> zigzagLevelOrder(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>>>(); zigzagLevelOrder(root, <span class="hljs-params">0</span>, ret); <span class="hljs-keyword">return</span> ret; } <span class="hljs-keyword">private</span>: <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">zigzagLevelOrder</span><span class="hljs-params">(<span class="hljs-keyword">const</span> 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>>>& ret)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-params">nullptr</span> || level < <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span>; <span class="hljs-keyword">if</span> (ret.size() <= level) { ret.push_back(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>()); } <span class="hljs-keyword">if</span> (level % <span class="hljs-params">2</span> == <span class="hljs-params">0</span>) ret[level].push_back(root->val); <span class="hljs-keyword">else</span> ret[level].insert(ret[level].begin(), root->val); zigzagLevelOrder(root->left, level + <span class="hljs-params">1</span>, ret); zigzagLevelOrder(root->right, level + <span class="hljs-params">1</span>, ret); } }; ``` ``` ## 相關題目 - [102.binary-tree-level-order-traversal](102.binary-tree-level-order-traversal.html) - [104.maximum-depth-of-binary-tree](104.maximum-depth-of-binary-tree.html)