Given an n-ary tree, return thepreordertraversal of its nodes' values.

For example, given a3-arytree:

Return its preorder traversal as:[1,3,5,6,2,4].

1.递归

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

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;

        helper(root, res);
        return res;
    }

    public void helper(Node root, List<Integer> res) {
        if(root == null)
            return;

        res.add(root.val);
        if(root.children != null && root.children.size() != 0) {
            for(Node n: root.children) {
                helper(n, res);
            }
        }
    }
}

2.非递归

非递归的做法麻烦一些，思路和binary tree preorder traversal 差不多，用一个stack储存之前遍历到的node，由于child可能多于2个，所以逻辑稍微复杂一些，对于stack中的node，每次检查从children中remove第一个child，只有在没有child之后才pop出stack

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

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;

        Stack<Node> stack = new Stack<Node>();
        Node p = root;
        stack.push(root);
        res.add(root.val);

        while(stack.size() > 0) {
            while(stack.size() > 0 && stack.peek().children.size() == 0)
                stack.pop();

            if(stack.size() == 0)
                break;

            p = stack.peek().children.remove(0);

            while(p != null) {
                res.add(p.val);
                stack.push(p);

                if(p.children != null && p.children.size() != 0) {
                    p = p.children.remove(0);
                } else {
                    p = null;
                }
            }
        }

        return res;
    }
}

3.leetcode solution也给出了一种做法

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

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;

        Stack<Node> stack = new Stack<Node>();
        stack.push(root);

        while(stack.size() > 0) {
            Node temp = stack.pop();
            res.add(temp.val);
            if(temp.children != null && temp.children.size() != 0) {
                for(int i = temp.children.size() - 1; i >= 0; i--) {
                    stack.push(temp.children.get(i));
                }
            }
        }

        return res;
    }
}