Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree
Given binary tree
[3,9,20,null,null,15,7]
,3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ret; helper(ret, 0, root); return ret; } void helper(vector<vector<int>>& ret, int level, TreeNode* node){ if(!node) return; if(ret.size()<level+1){ ret.resize(level+1); } ret[level].push_back(node->val); helper(ret, level+1, node->left); helper(ret, level+1, node->right); } }; <script class="brush: js" type="syntaxhighlighter"><![CDATA[ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ret; if(!root) return ret; queue<TreeNode*> que, que_tmp; que.push(root); vector<int> layer; while(!que.empty()){ TreeNode *node = que.front(); layer.push_back(node->val); que.pop(); if(node->left) que_tmp.push(node->left); if(node->right) que_tmp.push(node->right); if(que.empty()){ ret.push_back(layer); layer.clear(); que = que_tmp; que_tmp = queue<TreeNode*>(); } } return ret; } }; |
No comments:
Post a Comment