590. N-ary Tree Postorder Traversal

A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 590. N-ary Tree Postorder Traversal, the solution in this repository is mainly a stack solution.

Guide

What?

The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:

What state are we keeping?
How do we move from one state to the next?
When do we know the answer is already determined?

For this file, the main tools are: stack, sliding window.

Guide

When?

Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.

The important function names to track are _postorder, postorder.

Guide

Why?

The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.

The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.

Guide

How?

Walk through the solution in this order:

Read the setup variables first.
Follow the main loop or recursive helper next.
Watch where invalid states get skipped.
Check which value survives to the return statement.

The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.

Guide

Complexity

Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
Space: O(n) in the usual case for auxiliary containers or recursion

Guide

C++ Solution

Your submission

The accepted solution

solution.cpp

01/**
02Given an n-ary tree, return the postorder traversal of its nodes' values.
03
04For example, given a 3-ary tree:
05
06Return its postorder traversal as: [5,6,3,2,4,1].
07
08Note:
09
10Recursive solution is trivial, could you do it iteratively?
11**/
12
13//recursive
14//Your runtime beats 40.15 % of cpp submissions.
15/*
16// Definition for a Node.
17class Node {
18public:
19    int val;
20    vector<Node*> children;
21
22    Node() {}
23
24    Node(int _val, vector<Node*> _children) {
25        val = _val;
26        children = _children;
27    }
28};
29*/
30class Solution {
31public:
32    vector<int> ans;
33    void _postorder(Node* node){
34        if(node==NULL) return;
35        
36        for(Node* child : node->children){
37            _postorder(child);
38        }
39        
40        ans.push_back(node->val);
41    }
42    vector<int> postorder(Node* root) {
43        _postorder(root);
44        return ans;
45    }
46};
47
48//iterative
49//Your runtime beats 82.71 % of cpp submissions.
50/*
51// Definition for a Node.
52class Node {
53public:
54    int val;
55    vector<Node*> children;
56
57    Node() {}
58
59    Node(int _val, vector<Node*> _children) {
60        val = _val;
61        children = _children;
62    }
63};
64*/
65class Solution {
66public:
67    vector<int> postorder(Node* root) {
68        vector<int> ans;
69        stack<Node*> stk;
70        
71        stk.push(root);
72        
73        while(!stk.empty()){
74            Node* node = stk.top();
75            stk.pop();
76            
77            if(node==NULL)continue;
78            
79            for(Node* child : node->children){
80                stk.push(child);
81            }
82            
83            ans.insert(ans.begin(), node->val);
84        }
85        return ans;
86    }
87};
88
89/**
90Approach 1: Iterations
91Algorithm
92
93First of all, here is the definition of the TreeNode which we would use in the following implementation.
94
95Let's start from the root and then at each iteration pop the current node out of the stack and push its child nodes. 
96In the implemented strategy we push nodes into stack following the order Top->Bottom and Left->Right. 
97Since DFS postorder traversal is Bottom->Top and Left->Right the output list should be reverted after the end of loop.
98
99Complexity Analysis
100
101Time complexity : we visit each node exactly once, 
102thus the time complexity is O(N), where N is the number of nodes, i.e. the size of tree.
103
104Space complexity : depending on the tree structure, we could keep up to the entire tree, 
105therefore, the space complexity is O(N).
106**/

Cost

Complexity

Time

O(n) to O(n log n), depending on the dominant loop or data structure operation

Dominated by the main traversal, recursion, or data-structure operations in the code.

Space

O(n) in the usual case for auxiliary containers or recursion

Auxiliary state plus the answer structure where the problem requires one.