Sponsored
Sponsored
This approach utilizes recursion to traverse the N-ary tree in a postorder fashion. For each node, we recursively visit all its children first before processing the node itself.
Time Complexity: O(n), where n is the number of nodes, as each node is visited once.
Space Complexity: O(n) for the recursion stack in the worst case (maximum tree height).
1public class Node {
2 public int val;
3 public IList<Node> children;
4
5 public Node() {}
6
7 public Node(int _val) {
8 val = _val;
9 }
10
11 public Node(int _val, IList<Node> _children) {
12 val = _val;
13 children = _children;
14 }
15}
16
17public class Solution {
18 public IList<int> Postorder(Node root) {
19 List<int> result = new List<int>();
20 PostorderHelper(root, result);
21 return result;
22 }
23
24 private void PostorderHelper(Node node, List<int> result) {
25 if (node == null) return;
26 foreach (var child in node.children) {
27 PostorderHelper(child, result);
28 }
29 result.Add(node.val);
30 }
31}
32C# implementation leverages a recursive approach similar to other languages, utilizing a helper function PostorderHelper to recursively handle traversal. The root node is processed after all its children have been visited, adding the value to the result list.
This approach uses an iterative method to perform postorder traversal with the help of a stack to simulate recursion. Nodes are pushed onto the stack in such a way that their children are processed before the node itself.
Time Complexity: O(n)
Space Complexity: O(n)
1public 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) {
List<int> result = new List<int>();
if (root == null) return result;
Stack<Node> stack = new Stack<Node>();
stack.Push(root);
while (stack.Count > 0) {
Node node = stack.Pop();
result.Insert(0, node.val);
foreach (var child in node.children) {
if (child != null) stack.Push(child);
}
}
return result;
}
}
C# implementation utilizes a stack approach to perform postorder traversal. As nodes are processed, they are inserted at the start of the result list, ensuring all children are handled first. The order in which nodes are popped and added grants postorder upon completion.