Given the root of an n-ary tree, return the postorder 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: [5,6,3,2,4,1]
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: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]
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 create a helper function that takes two arguments, the current Node and the list to populate the elements in the Postorder Traversal. In the helper, first we iterate through all the Node’s children and recursively call itself with each child. Then we add the current Node’s element to the list. In the main function, we check if the node is null, in which case we return an empty list. Otherwise we just call the helper with the root and our list and finally return the output list.
Time complexity is O(n), where n is the number of elements in the tree because we visit all nodes once. Space complexity is O(n) due to the space required for the 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> postorder(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) {
for (int i = 0; i < root.children.size(); i++) {
helper(root.children.get(i), list);
}
list.add(root.val);
}
}