> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/tree/590.-n-ary-tree-postorder-traversal.md).

# 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&#x20;

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

\=>得到答案

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

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MD-wl_kvpvednMhShZC%2F-MD-wp-ijKXmY5-AfHXD%2Fimage.png?alt=media\&token=745445de-4b4b-46f1-a49f-df1fa0794467)

```java

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

```java
/*
// 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);
    }
}
```