###### tags: `LeetCode` `Recursion` `Postorder` `Iterative` `Medium` `Easy` `Tree` `Stack`
# LeetCode #590 [N-ary Tree Postorder Traversal](https://leetcode.com/problems/n-ary-tree-postorder-traversal/)
### (Easy):Recursion (Medium):Iterative
給定一個 N 元樹，返回其節點值的後序遍歷 。

N 元樹 在輸入中按層序遍歷進行序列化表示，每組子節點由空值 null 分隔（請參見示例）。

---
遞迴法:

很簡單, 先處理完子節點再將根節點的值放入數組。

class Solution {
public:
    vector<int> postorder(Node* root) {
        if(root==nullptr)return {};
        vector<int> nodes;
        helper(root, nodes);
        return nodes;
    }
    void helper(Node* root, vector<int>& nodes){
        if(root==nullptr)return;
        for(Node* child:root->children)
            helper(child, nodes);
        nodes.push_back(root->val);
    }
};

---
迭代法:

由於postorder的表示是左子節點->右子節點->根節點, 但是必須要先存取根結點才有辦法使用他的(左右)子節點, 這兩件事按照常理來說是衝突的(先pop出來的元素在最後表示時卻是在數組的尾端), 而解決衝突的辦法就是數組反著插入, 由末端插入變成前端插入, 這樣最早插入的數會在數組的尾端。

而由於postorder的子節點表現先後順序為左至右, 以常理來說堆疊插入應該先右後左(也就是root->children[root->children.size()-1]往root->children[0])插入, 但由於輸出反向了, 所以堆疊的插入也變為先左後右。

class Solution {
public:
    vector<int> postorder(Node* root) {
        if(root){
            stack<Node*> s;
            vector<int> nodes;
            s.push(root);
            while(!s.empty()){
                Node* cur=s.top();s.pop();
                nodes.insert(nodes.begin(), cur->val);
                for(int i=0;i<cur->children.size();i++){
                    s.push(cur->children[i]);
                }
            }
            return nodes;
        }
        return {};
    }
    
};