Question

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?

Solution:

  • Method 1: dfs 
    /*
// 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 {
    private List<Integer> result;
    public List<Integer> postorder(Node root) {
        this.result = new ArrayList<>();
        if(root == null) return this.result;
        dfs(root);
        return this.result;
    }
    private void dfs(Node node){
        for(int i = 0; i < node.children.size(); i++){
            dfs(node.children.get(i));
        }
        result.add(node.val);
    }
}
  • Method 2: Iteration 
    /*
// 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> 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);
            for(int i = 0; i < node.children.size(); i++){
                stack.push(node.children.get(i));
            }
        }
        Collections.reverse(result);
        return result;
    }
}