共计 1215 个字符，预计需要花费 4 分钟才能阅读完成。
题目
Given an n-ary tree, return the preorder traversal of its nodes’ values.
For example, given a 3-ary tree:
Return its preorder traversal as: [1,3,5,6,2,4].
Note:
Recursive solution is trivial, could you do it iteratively?
题目地址
讲解
如果用递归来解题的话，还是非常简单的。如果要用迭代来解题，无非就是用栈来实现。要注意的一点是，需要一个额外的栈来把压栈的顺序倒一下序。
Java 代码
递归代码：
/*
// 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 {
private List<Integer> result = new ArrayList<>();
public List<Integer> preorder(Node root) {
if(root==null){
return result;
}
result.add(root.val);
for(Node node:root.children){
preorder(node);
}
return result;
}
}
迭代代码：
/*
// 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 {
private List<Integer> result = new ArrayList<>();
private Stack<Node> stack = new Stack<>();
private Stack<Node> stack_temp = new Stack();
public List<Integer> preorder(Node root) {
if(root==null){
return result;
}
stack.push(root);
while(!stack.empty()){
Node theNode = stack.pop();
result.add(theNode.val);
for(Node node:theNode.children){
stack_temp.push(node);
}
while(!stack_temp.empty()){
stack.push(stack_temp.pop());
}
}
return result;
}
}
