429.N Ary Tree Level Order Traversal
429.N ary Tree Lever Order Traversal
难度:Easy
给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。
例如,给定一个 3叉树 :
narytreeexample.png
返回其层序遍历:
1
[
2
[1],
3
[3,2,4],
4
[5,6]
5
]
Copied!
说明:
树的深度不会超过 1000。 树的节点总数不会超过 5000。
方法:采用了队列的先进后出,迭代遍历所有节点。
1
/*
2
// Definition for a Node.
3
class Node {
4
public:
5
int val;
6
vector<Node*> children;
7
8
Node() {}
9
10
Node(int _val, vector<Node*> _children) {
11
val = _val;
12
children = _children;
13
}
14
};
15
*/
16
class Solution {
17
public:
18
vector<vector<int>> levelOrder(Node* root) {
19
deque<Node*> d;
20
vector<vector<int>> res;
21
if(!root)
22
return res;
23
24
d.push_back(root);
25
while(!d.empty())
26
{
27
vector<int >tmp;
28
for(auto i: d)
29
tmp.push_back(i->val);
30
int len=d.size();
31
while(len--)
32
{
33
if(d[0]->children.empty())
34
d.pop_front();
35
else
36
{
37
38
for(auto i: d[0]->children)
39
d.push_back(i);
40
d.pop_front();
41
}
42
}
43
res.push_back(tmp);
44
45
}
46
return res;
47
48
}
49
};
Copied!
Copy link