leetcode 590. N叉树的后序遍历
题目描述:
给定一个 N 叉树,返回其节点值的后序遍历。
例如,给定一个 3叉树
:
返回其后序遍历: [5,6,3,2,4,1]
.
代码:
递归版本:
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> list=new ArrayList<>();
if(root==null)
return list;
for(int i=0;i<root.children.size();i++){
list.addAll(postorder(root.children.get(i)));
}
list.add(root.val);
return list;
}
}
非递归版本:
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> list=new ArrayList<>();
if(root==null)
return list;
Stack<Node> st1=new Stack<>();
Stack<Node> st2=new Stack<>();
st1.push(root);
while(!st1.isEmpty()){
Node head=st1.pop();
st2.push(head);
for(int i=0;i<head.children.size();i++){
st1.push(head.children.get(i));
}
}
while(!st2.isEmpty()){
list.add(st2.pop().val);
}
return list;
}
}