题目链接:Binary Tree Level Order Traversal
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]
]
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.
OJ’s Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.
这道题的要求是分层遍历二叉树。
由于需要把每层的节点分别放入到数组中,因此需要引入变量n记录每层的节点数量。剩下的,就是广度优先搜索的方法了。
广度优先搜索算法(Breadth First Search),又叫宽度优先搜索,或横向优先搜索。从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。借助队列数据结构,由于队列是先进先出的顺序,因此可以先将左子树入队,然后再将右子树入队。这样一来,左子树结点就存在队头,可以先被访问到。
时间复杂度:O(n)
空间复杂度:O(n)
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
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root)
{
vector<vector<int> > vvi;
if(NULL == root)
return vvi;
queue<TreeNode *> q;
q.push(root);
while(!q.empty())
{
vector<int> vi;
for(int i = 0, n = q.size(); i < n; ++ i)
{
TreeNode *temp = q.front();
q.pop();
if(temp -> left != NULL)
q.push(temp -> left);
if(temp -> right != NULL)
q.push(temp -> right);
vi.push_back(temp -> val);
}
vvi.push_back(vi);
}
return vvi;
}
};