https://leetcode.com/problems/n-ary-tree-postorder-traversal/
Given an n-ary tree, return the postorder traversal of its nodes' values.
For example, given a
3-ary tree:
Return its postorder traversal as:
[5,6,3,2,4,1].
Note:
Recursive solution is trivial, could you do it iteratively?
The iterative solution is similar to the pre-order's, except for when to add the root to the list. The second stack is usd to store the node that pops from the first stack.
public List<Integer> postorder(Node root) {
List<Integer> list = new ArrayList<Integer>();
if(root == null) return list;
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.add(root);
while(!stack1.empty())
{
Node top = stack1.pop();
stack2.push(top);
for(int i = 0; i < top.children.size(); i++)
stack1.push(top.children.get(i));
}
while(!stack2.empty())
list.add(stack2.pop().val);
return list;
}https://leetcode.com/problems/n-ary-tree-postorder-traversal/discuss/147959/Java-Iterative-and-Recursive-Solutions
public List<Integer> postorder(Node root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;
Stack<Node> stack = new Stack<>();
stack.add(root);
while(!stack.isEmpty()) {
root = stack.pop();
list.add(root.val);
for(Node node: root.children)
stack.add(node);
}
Collections.reverse(list);
return list;
}
}
Recursive
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> postorder(Node root) {
if (root == null)
return list;
for(Node node: root.children)
postorder(node);
list.add(root.val);
return list;
}
