589. N叉树的前序遍历

题目描述

原题

给定一个 N 叉树,返回其节点值的前序遍历

例如,给定一个 3叉树 :

返回其前序遍历: [1,3,5,6,2,4]

说明: 递归法很简单,你可以使用迭代法完成此题吗?

题解

递归解法

class Solution {
public List<Integer> preorder(Node root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
list.add(root.val);
List<Node> children = root.children;
if(children!=null){
for(Node child : children){
list.addAll(preorder(child));
}
}
return list;
}
}

迭代解法

class Solution {
public List<Integer> preorder(Node root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
LinkedList<Node> stack = new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
list.add(root.val);
List<Node> children = root.children;
if(children!=null){
for(int i = children.size() - 1;i >= 0;i--){
stack.push(children.get(i));
}
}
}
return list;
}
}