Given the root of an n-ary tree, return the preorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)
Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]
Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]
Constraints:
- The number of nodes in the tree is in the range [0, 104].
- 0 <= Node.val <= 104
- The height of the n-ary tree is less than or equal to 1000.
My Solution
We can create a helper function that takes two arguments, the N-ary Tree Node and the preorder traversal ArrayList. We first add the current node’s value to the ArrayList. We then iterate through all the node’s children and call the helper on those nodes in succession. In our main function, we call our helper and take care of the special case that there are no elements in the N-ary tree.
Time complexity is O(n), where n is the number of elements in the tree because we visit all the nodes once. Space complexity is O(n) for the space required for output preorder traversal list.
/*
// 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> preorder(Node root) {
List<Integer> out = new ArrayList<>();
if (root == null) {
return out;
}
helper(root, out);
return out;
}
public void helper(Node root, List<Integer> list) {
list.add(root.val);
for (int i = 0; i < root.children.size(); i++) {
helper(root.children.get(i), list);
}
}
}