590. N-ary Tree Postorder Traversal

Given an n-ary tree, return the postorder traversal of its nodes' values.Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

recursion DFS

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

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

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }
    private void dfs(Node node, List<Integer> list){
        if (node ==null) return;
        for(Node child : node.children){
            dfs(child,list);
        }
        list.add(node.val);
    }
}

Iteration

class Solution {
    public List<Integer> postorder(Node root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root ==null) return res;
        Stack<Node> stack = new Stack<>();
        stack.add(root);
        while(!stack.isEmpty()){
          Node node = stack.peek();
          if (node.children==null){
              res.add(stack.pop().val);
              continue;
          }         
          for(int i = node.children.size()-1;i>=0;i--){
              stack.push(node.children.get(i));
          }
          node.children=null;
        }
        return res;   
    }
}

improvement using Linkedlist instead of Stack

class Solution {
    public List<Integer> postorder(Node root) {
        LinkedList<Integer> res = new LinkedList<>();
        LinkedList<Node> stack = new LinkedList<>();
        if (root == null) return res;
        stack.add(root);
        while(!stack.isEmpty()){
            // pop the left most node out 
            Node node = stack.pollLast();
            // parent value must shown after the children's value
            // right value must shown after the left value
            res.addFirst(node.val);
            for(Node child: node.children){
                // add each child node to the end of list
                // left child will be added before the right child
                stack.add(child);
            }
        }
        return res;
    }
}