###### tags: `Leetcode` `easy` `tree` `dfs` `python` `c++`

# 590. N-ary Tree Postorder Traversal

## [題目連結:] https://leetcode.com/problems/n-ary-tree-postorder-traversal/description/

## 題目:
Given the ```root``` of an n-ary tree, return the postorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

**Follow up**: Recursive solution is trivial, could you do it iteratively?


## 解題想法:
* 同類型題目: [589. N-ary Tree Preorder Traversal](/t0AHML8AQBeGhDb6Bzc6rQ)

* 題目為: 給N-ary Tree，求Postorder traversal(左右中)
* val: Node.val
* children: 為list，存該root下一層所有child Node

## Python_Sol1: Recursive
* 遞迴: 遞迴遍歷到底，再存root.val

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        def dfs(root):
            if not root:
                return 
            for child in root.children:
                dfs(child)
            res.append(root.val)
        res=[]
        dfs(root)
        return res

## Python_Sol2: Iterative
* Postorder: 左右中-> 想成 **中右左+reverse**

class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if not root:
            return 
        stack=[root]
        res=[]
        while stack:
            curRoot=stack.pop()
            res.append(curRoot.val)
            for child in curRoot.children:
                stack.append(child)
        return res[::-1]

## C++: Recursive

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

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

## C++: Iterative:

class Solution {
public:
    vector<int> postorder(Node* root) {
        stack<Node*> NodeStack;
        vector<int> res;
        if (root==nullptr)
            return res;
        NodeStack.push(root);
        Node* curRoot=nullptr;
        while (!NodeStack.empty()){
            curRoot=NodeStack.top(); NodeStack.pop();
            res.push_back(curRoot->val);
            for (Node* child: curRoot->children){
                NodeStack.push(child);
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};