Leetcode题解
Search…
589.N Ary Tree Preorder Traversal
589.N Ary Tree Preorder Traversal
难度:Easy
给定一个 N 叉树，返回其节点值的前序遍历。
例如，给定一个 3叉树 : 
返回其前序遍历: [1,3,5,6,2,4]。
代码如下：
- 递归版本:
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<int> preorder(Node* root) {
19
vector<int >res;
20
if(!root) return res;
21
res.push_back(root->val);
22
for(auto i:root->children)
23
{
24
vector<int>tmp=preorder(i);
25
res.insert(res.end(),tmp.begin(),tmp.end());
26
}
27
return res;
28
}
29
};
Copied!
- 迭代版本:
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<int> preorder(Node* root) {
19
vector<int>res;
20
if(!root) return res;
21
stack<Node*>pt;
22
pt.push(root);
23
res.push_back(root->val);
24
while(!pt.empty())
25
{
26
if(pt.top()->children.empty())
27
{
28
pt.pop();
29
if(!pt.empty()) pt.top()->children.erase(pt.top()->children.begin());
30
}
31
else{
32
33
pt.push(pt.top()->children[0]);
34
res.push_back(pt.top()->val);
35
}
36
}
37
return res;
38
}
39
};
Copied!
Copy link