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

For example, given a3-arytree:

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

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> postorder(Node root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;

        helper(res, root);
        return res;
    }

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

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

2.非递归，还是需要一个stack，思路类似N-ary tree preorder travsersal

/*
// 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> postorder(Node root) {
        LinkedList<Integer> res = new LinkedList<Integer>();
        if(root == null)
            return res;

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

        while(stack.size() > 0) {
            Node temp = stack.pop();
            res.offerFirst(temp.val);

            if(temp.children != null && temp.children.size() != 0) {
                for(Node node: temp.children) {
                    stack.push(node);
                }
            }
        }

        return res;
    }
}