[Leetcode] Binary Tree Level Order Traversal

<div class="iteye-blog-content-contain" style="font-size: 14px;"> <div id="question_102" class="row-even question-title" style="margin: 0px; padding: 5px 8px; border: 1px solid #ffffff; font-size: 13px; vertical-align: baseline; cursor: pointer; color: #222222; font-family: 'Helvetica Neue', arial, sans-serif;"> <strong style="margin: 0px; padding: 0px; border: 0px; vertical-align: baseline; background-color: transparent;">Binary Tree Level Order Traversal</strong><span class="date" style="margin: 0px 10px 0px 0px; padding: 0px; border: 0px; font-size: 10px; vertical-align: baseline; background-color: transparent; color: #999999; float: right;" title="2012-09-29 03:19:48">Sep 29 '12</span><span class="stats" style="margin: 0px; padding: 1px 4px; border: 0px; font-size: 11px; vertical-align: baseline; background-color: #eeeeee; color: #999999; width: 65px; text-align: center;" title="5832 accepted submissions out of 14746 (40%)">5832 / 14746</span> </div> <div class="row-even question-content" style="margin: 0px; padding: 5px 8px 5px 55px; border: 1px solid #ffffff; font-size: 13px; vertical-align: baseline; color: #222222; font-family: 'Helvetica Neue', arial, sans-serif;"> <p style="margin-bottom: 20px; border: 0px; vertical-align: baseline; background-color: transparent;">Given a binary tree, return the <em style="margin: 0px; padding: 0px; border: 0px; vertical-align: baseline; background-color: transparent;">level order</em> traversal of its nodes' values. (ie, from left to right, level by level).</p> <p style="margin-bottom: 20px; border: 0px; vertical-align: baseline; background-color: transparent;">For example:<br style="margin: 0px;">Given binary tree <code style="margin: 0px; padding: 1px 5px; border: 0px; font-size: 13px; vertical-align: baseline; background-color: #eeeeee; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif;">{3,9,20,#,#,15,7}</code>,</p> <pre> 3 / \ 9 20 / \ 15 7 </pre> <p style="margin-bottom: 20px; border: 0px; vertical-align: baseline; background-color: transparent;"> </p> <p style="margin-bottom: 20px; border: 0px; vertical-align: baseline; background-color: transparent;">return its level order traversal as:</p> <pre>[ [3], [9,20], [15,7] ]</pre> </div> <p> </p> <pre name="code" class="cpp">/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector&lt;vector&lt;int&gt; &gt; levelOrder(TreeNode *root) { vector&lt;vector&lt;int&gt; &gt; res; if (root == NULL) return res; queue&lt;TreeNode*&gt; q; int cur = 1, next = 0; q.push(root); vector&lt;int&gt; a; while (!q.empty()) { auto tmp = q.front(); q.pop(); a.push_back(tmp-&gt;val); cur--; if (tmp-&gt;left != NULL) q.push(tmp-&gt;left), next++; if (tmp-&gt;right != NULL) q.push(tmp-&gt;right), next++; if (cur == 0) { cur = next; next = 0; res.push_back(a); a.clear(); } } //if (a.size() &gt; 0) res.push_back(a); return res; } };</pre> <p> </p> </div>