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,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
我使用的是广搜,要用到队列。但由于是二叉树,可以时间效率更高的方法,dfs遍历,标记每个节点的顺序,1,2,3,4 空节点就跳过。在相应顺序为下标中的数组中插入相应的值。
然后1 , 2 3 ,4 5 6 7 8 ,...按照这个规律插到二维数组中。
c++ 广搜
lass Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
queue<int> q2;
vector<vector<int> > ans;
if(root==NULL)
return ans;
q.push(root);q2.push(0);
vector<int> res;
int j=-1;
while(!q.empty())
{
TreeNode* term = q.front();
int i = q2.front();
if(i==j+2)
{
ans.push_back(res);
res.clear();
j++;
}
res.push_back(term->val);
q.pop();q2.pop();
if(term->left!=NULL)
{ q.push(term->left);q2.push(i+1);}
if(term->right!=NULL)
{ q.push(term->right);q2.push(i+1);}
}
if(!res.empty())
ans.push_back(res);
return ans;
}
};