[LeetCode] Problem 590 - N-ary Tree Postorder Traversal

Posted on | In ,

Given an n-ary tree, return the postorder traversal of its nodes’ values.

For example, given a 3-ary tree:

E69bqA.png

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

Note

Recursive solution is trivial, could you do it iteratively?

Code

1
2
3
4
5
6
7
8
public class Node {
    public int val;
    public List<Node> children;
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> postorder(Node root) {
    List<Integer> result = new ArrayList<>();

    if (root == null)
        return result;

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

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        result.add(0, node.val);
        List<Node> children = node.children;

        for (Node child : children)
            stack.push(child);
    }

    return result;
}