[LeetCode] Problem 589 - N-ary Tree Preorder Traversal

Posted on | In ,

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

For example, given a 3-ary tree:

E69bqA.png

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

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> preorder(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(node.val);
        List<Node> children = node.children;

        for (int i = children.size() - 1; i >= 0; i--)
            stack.push(children.get(i));
    }

    return result;
}