首页 > itarticle > [leetcode] problem 589 – n-ary tree preorder traversal

[leetcode] problem 589 – n-ary tree preorder traversal

admin 11月 13, 2020 0

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

For example, given a 3-ary tree:

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

Note

Recursive solution is trivial, could you do it iteratively?

Code

public class  {
    public int val;
    public List<Node> children;
    public (int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

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;
}