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

# 589. N-ary Tree Preorder Traversal

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

## 題目:
Given the ```root``` of an n-ary tree, return the preorder 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?


## 解題想法:
* 同類型題目: [590. N-ary Tree Postorder Traversal](/9lLTU7JrQCKIXQGVNCerMw)
* 題目為: 給N-ary Tree，求Preorder traversal(中左右)
* val: Node.val
* children: 為list，存該root下一層所有child Node

## Python_Sol1: Recursive
* 遞迴: 將root加到res，逐一遍歷所有子數

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

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

## Python_Sol2: Iterative
* 使用stack裝node
* 正常pop出最尾的
* 對於children list，**需先反轉**才能逐一將node存入
* 因為每次要先用左子

class Solution(object):
    def preorder(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[::-1]:
                stack.append(child)
        return res

## C++ Sol1: 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> preorder(Node* root) {
        dfs(root);
        return res;
    }

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

## C++ Sol2: Iterative

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