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 {3,9,20,#,#,15,7}
,
3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
层序遍历一颗二叉树,借助一个队列就可以了
为了偷懒简写,注意我定义了几个#define 字符替换
代码比较易懂,我就不解释了。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ #define vi vector<int> #define vvi vector<vi > #define tr TreeNode class Solution { public: vvi levelOrder(tr* root) { vvi ans; if (!root) return ans; vi curLevel; queue<TreeNode*> Q; Q.push(root); int cur=1,next=0; while(!Q.empty()) { while(cur--) { tr* tmp=Q.front(); Q.pop(); curLevel.push_back(tmp->val); if (tmp->left) { Q.push(tmp->left); next++; } if (tmp->right) { Q.push(tmp->right); next++; } } ans.push_back(curLevel); curLevel.clear(); cur=next; next=0; } return ans; } };