590.N Ary Tree Postorder Traversal
590.N Ary Tree Postorder Traversal
难度:Easy
给定一个 N 叉树,返回其节点值的后序遍历。
例如,给定一个 3叉树 :
返回其后序遍历: [5,6,3,2,4,1].
说明: 递归法很简单,你可以使用迭代法完成此题吗?
  • 递归法:
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> postorder(Node* root) {
19
vector<int>res;
20
if(!root) return res;
21
for(auto i:root->children)
22
{
23
vector<int>tmp =postorder(i);
24
res.insert(res.end(),tmp.begin(),tmp.end());
25
}
26
res.push_back(root->val);
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> postorder(Node* root) {
19
vector<int>res;
20
if(!root) return res;
21
stack<Node*>pt;
22
pt.push(root);
23
while(!pt.empty())
24
{
25
if(pt.top()->children.empty())
26
{
27
res.push_back(pt.top()->val);
28
pt.pop();
29
if(!pt.empty()) pt.top()->children.erase(pt.top()->children.begin());
30
}
31
else{
32
pt.push(pt.top()->children[0]);
33
}
34
}
35
return res;
36
}
37
};
Copied!
Copy link