N-ary Tree Postorder Traversal
Tree
Easy
Given an n-ary tree, return thepostordertraversal of its nodes' values.
For example, given a3-ary
tree:

Return its postorder traversal as:[5,6,3,2,4,1]
.
Note:
Recursive solution is trivial, could you do it iteratively?
Solution
Iterative - with stack
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> postorder(Node root) {
LinkedList<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
LinkedList<Node> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
res.addFirst(node.val);
if (node.children != null) {
for (Node c: node.children) {
if (c != null) {
stack.push(c);
}
}
}
}
return res;
}
}
Complexity Analysis
Time complexity : we visit each node exactly once, thus the time complexity is O(N), where N is the number of nodes, _i.e._ the size of tree.
Space complexity : depending on the tree structure, we could keep up to the entire tree, therefore, the space complexity is O(N).
Recursive
class Solution {
public List<Integer> postorder(Node root) {
LinkedList<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
postorderHelper(root, res);
return res;
}
private void postorderHelper(Node root, List<Integer> res) {
if (root == null) {
return;
}
if (root.children != null) {
for (Node c : root.children) {
postorderHelper(c, res);
}
}
res.add(root.val);
}
}
Last updated
Was this helpful?