Given 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).
Recursive solution is trivial, could you do it iteratively?
Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]
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]
- The height of the n-ary tree is less than or equal to 1000
- The total number of nodes is between [0, 10^4]
-
java
/* // 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; } }; */
- mine
Runtime: 2 ms, faster than 48.85%, Memory Usage: 40.4 MB, less than 100.00% of Java online submissions
// O(N)time O(N)space, N is the node count. class Solution { public List<Integer> preorder(Node root) { List<Integer> res = new ArrayList<>(); if(root == null){ return res; } res.add(root.val); if(root.children != null && root.children.size() > 0){ for(Node n : root.children){ res.addAll(preorder(n)); } } return res; } }
- mine