Problem：

Given an n-ary tree, return the preorder traversal of its nodes' values.

Explanation：

对n叉树进行前序遍历。

My Thinking：

1. 使用递归，在二叉树的基础上对每个结点的孩子进行遍历递归。
2. 使用栈进行迭代，

My Solution：

（1）

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> result=new ArrayList<>();
        return recursive(root,result);
    }
    public List<Integer> recursive(Node node,List<Integer> result){
        if(node==null)
            return result;
        result.add(node.val);
        for(Node i:node.children){
           recursive(i,result);  
        }
        return result;
    }
}

（2）

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> result=new ArrayList<>();
        Stack<Node> stack=new Stack<>();
        if(root==null)
            return result;
        Node node=root;
        stack.push(root);
        
        while(!stack.isEmpty()){
            node=stack.pop();
            result.add(node.val);
            for(int i=node.children.size()-1;i>=0;i--){
                stack.push(node.children.get(i));
            }
        }
        return result;
    }
}

Optimum Thinking:

Optimum Solution：