题目描述：
Given an n-ary tree, return the postorder traversal of its nodes' values.
For example, given a 3-ary tree:
Return its postorder traversal as: [5,6,3,2,4,1].
class Solution { public: vector<int> postorder(Node* root) { if(root==NULL) return {}; if(root->children.size()==0) return {root->val}; vector<int> result; unordered_map<Node*,int> next_child; stack<Node*> s; s.push(root); Node* p=root; while(!s.empty()) { if(next_child.count(p)==0) next_child[p]=0; int i=next_child[p]; next_child[p]++; if(i==p->children.size()) { result.push_back(p->val); next_child.erase(p); p=s.top(); s.pop(); } else { s.push(p); p=p->children[i]; } } return result; } }; class Solution { public: vector<int> postorder(Node* root) { if(root==NULL) return {}; vector<int> result; stack<Node*> s; s.push(root); // 后序遍历先访问第一个子节点到最后一个子节点，然后是父节点 // 用栈模拟的时候可以先访问父节点，再访问最后一个子节点，到第一个子节点 while(!s.empty()) { Node* cur=s.top(); s.pop(); result.push_back(cur->val); for(int i=0;i<cur->children.size();i++) s.push(cur->children[i]); // 正着将所有子节点压栈，那么栈顶是最后一个子节点 } // 最后将结果翻转得到正确的顺序 reverse(result.begin(),result.end()); return result; } };
