424. N-ary Tree Preorder Traversal
You are given the root of an n-ary tree: every node carries an integer val and an ordered list children holding any number of child nodes (a Node object, or None for an empty tree).
Return the preorder traversal of the tree as a list of values: record a node the moment you arrive at it, then walk through its children from left to right, applying the same rule inside each child's subtree.
The raw input serializes the tree in level order by groups — the root value, a null, then each node's children in turn with a null closing every group — but the harness parses that for you; your function receives ready-made Node objects.
Example 1:
Input: root = [1, null, 3, 2, 4, null, 5, 6]
Output: [1, 3, 5, 6, 2, 4]
Explanation: Start at the root 1, then fully explore its first child 3 (which visits 5 and 6) before moving on to siblings 2 and 4.
Example 2:
Input: root = [8, null, 3, 6, 9, null, 4, 5, null, null, 7]
Output: [8, 3, 4, 5, 6, 9, 7]
Explanation: After the root 8, the subtree of 3 contributes 3, 4, 5; the childless 6 is next; finally 9 and its child 7.
Constraints:
- 0 ≤ number of nodes ≤ 10⁴
- 0 ≤ Node.val ≤ 10⁴
- The height of the tree is at most 1000
Hints:
Preorder means "me first, then my subtrees in order". Write a helper that appends the node's value and then recurses into each child left to right.
For the iterative version, use an explicit stack: pop a node, record it, then push its children in REVERSE order — that way the leftmost child comes off the stack first.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, null, 3, 2, 4, null, 5, 6]
Expected output: [1, 3, 5, 6, 2, 4]