LeetCode-590. N叉树的后序遍历

给定一个 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: vector<int> postorder(Node* root) { 
18         vector<int> ans; 
19         if(root==NULL) return ans; 
20         postord(root,ans); 
21         return ans; 
22     } 
23     void postord(Node* root, vector<int> &ans) { 
24         if(root==NULL) return; 
25         for(int i=0;i<root->children.size();i++) { 
26             postord(root->children[i],ans); 
27         } 
28         ans.push_back(root->val); 
29     } 
30 };

迭代法：

 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> ans; 
20         if(root==NULL) 
21             return ans; 
22         stack<Node*> s; 
23         s.push(root); 
24         Node* node; 
25         while(!s.empty()) { 
26             node=s.top(); 
27             s.pop(); 
28             for(int i=0;i<node->children.size();i++) { 
29                 s.push(node->children[i]); 
30             } 
31             ans.push_back(node->val); 
32         } 
33         reverse(ans.begin(),ans.end()); 
34         return ans;
35     }
36 };

没啥可说的，emmm……

LeetCode-590. N叉树的后序遍历

相关推荐