题目:
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] ]
题目解答:这个题目非常简单,就是二叉树的层次遍历。需要两个整型的临时变量分别记录当前层的节点数目和下一层的节点数目。使用队列来存储这个二叉树节点遍历的先后顺序。
代码:
/**
* 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) {
int curnum = 0;
int childnum = 0;
vector<vector<int> > res;
if(root == NULL)
{
return res;
}
queue<TreeNode *> TreeQueue;
TreeQueue.push(root);
curnum = 1;
while(curnum != 0)
{
vector<int> tmp;
while(curnum != 0)
{
TreeNode *p = TreeQueue.front();
tmp.push_back(p -> val);
if(p -> left != NULL)
{
TreeQueue.push(p -> left);
childnum++;
}
if(p -> right != NULL)
{
TreeQueue.push(p -> right);
childnum++;
}
TreeQueue.pop();
curnum--;
}
res.push_back(tmp);
curnum = childnum;
childnum = 0;
}
return res;
}
};