590. N-ary Tree Postorder Traversal

https://leetcode.com/problems/n-ary-tree-postorder-traversal/

preorder: root left right

so postorder: left right root

=> root right left

=> reverse ( use linkedList addFirst(), 注意要用這個要頭尾都宣告純 LinkedList<> list = new LinkedList<>() 才會有這個方法

=>得到答案

O(M), O(M) M is the total nodes of this tree

class Solution {
    public List<Integer> postorder(Node root) {
        // because preorder is root left right
        // postorder is left right root
        // so root right left then reverse is postorder
        // to acheive reverse we can push (addFirst) to LinkedList
        
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        
        Stack<Node> stack = new Stack<>();
        stack.add(root);
        
        while (!stack.isEmpty()) {
            Node node = stack.pop(); // pop right then left
            if (node != null) {
                res.addFirst(node.val); // add first, so it would be left right root
                for (Node n : node.children) {
                    stack.push(n); // push left right
                }
            }
        }
        return res;
    }
}

recursive

/*
// 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<>();
        helper(root, res);
        return res;
    }
    private void helper(Node root, List<Integer> res) {
        if (root == null) {
            return;
        }
        for (Node node : root.children) {
            helper(node, res);
        }
        res.add(root.val);
    }
}