首页 > itarticle > [leetcode] problem 590 – n-ary tree postorder traversal

[leetcode] problem 590 – n-ary tree postorder traversal

admin 11月 13, 2020 0

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

For example, given a 3-ary tree:

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

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