Sponsored
Sponsored
This approach leverages the simplicity of recursion to perform a preorder traversal on an n-ary tree. We start at the root node, then recursively process each child's subtree.
Time Complexity: O(n), where n is the number of nodes in the tree, since we visit each node once.
Space Complexity: O(n) for the recursion stack used in the helper function.
1import java.util.ArrayList;
2import java.util.List;
3
4class Node {
5 public int val;
6 public List<Node> children;
7
8 public Node() {}
9
10 public Node(int _val) {
11 val = _val;
12 }
13
14 public Node(int _val, List<Node> _children) {
15 val = _val;
16 children = _children;
17 }
18};
19
20class Solution {
21 public List<Integer> preorder(Node root) {
22 List<Integer> result = new ArrayList<>();
23 preorderHelper(root, result);
24 return result;
25 }
26
27 public void preorderHelper(Node node, List<Integer> result) {
28 if (node == null) return;
29 result.add(node.val);
30 for (Node child : node.children) {
31 preorderHelper(child, result);
32 }
33 }
34}The Java code defines a class structure for the Node with value and list of children. The preorderHelper method recursively traverses the node, first adding the node's value to the result list, then invoking itself on all child nodes.
This approach uses an explicit stack to simulate the call stack of recursion. We manually manage traversals seen in recursion, starting from the root node, iteratively processing each node, then adding each child to a stack for future visits.
Time Complexity: O(n). Space Complexity: O(n), as most nodes can be stored in the stack in the worst case.
1
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> Preorder(Node root) {
var result = new List<int>();
if (root == null)
return result;
Stack<Node> stack = new Stack<Node>();
stack.Push(root);
while (stack.Count > 0) {
Node currentNode = stack.Pop();
result.Add(currentNode.val);
for (int i = currentNode.children.Count - 1; i >= 0; i--) {
stack.Push(currentNode.children[i]);
}
}
return result;
}
}The Solution in C# leverages the Stack provided in .NET to manually handle traversal operations to achieve preorder. This implementation adheres to order by reversing it when adding children to the stack.