590. N-ary Tree Postorder Traversal
Approach
Iterative reverse-preorder: collect root, then process children
left-to-right; the reversed result gives postorder.
Key Techniques
Stacks support LIFO (last-in, first-out) operations in O(1). Key patterns: balanced parentheses, next greater element (monotonic stack), function call simulation, and undo/redo. A monotonic stack maintains a strictly increasing or decreasing order to answer range queries efficiently.
Tree problems typically require recursive DFS or iterative BFS. Common patterns: preorder for serialization, inorder for BST sorted output, postorder for bottom-up aggregation. Always consider edge cases: null nodes, single-node trees, and skewed (list-like) trees.
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
// Approach: Iterative reverse-preorder: collect root, then process children
// left-to-right; the reversed result gives postorder.
// Time: O(n) Space: O(n)
public class Node
{
public int val;
public IList<Node> children;
public Node() { }
public Node(int _val)
{
val = _val;
}
public Node(int _val, IList<Node> _children)
{
val = _val;
children = _children;
}
}
public class Solution
{
public IList<int> Postorder(Node root)
{
if (root == null)
return new List<int>();
List<int> ans = new List<int>();
Stack<Node> stack = new Stack<Node>();
stack.Push(root);
while (stack.Count > 0)
{
root = stack.Pop();
ans.Add(root.val);
foreach (Node child in root.children)
stack.Push(child);
}
ans.Reverse();
return ans;
}
}