问题
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4090 访问。
给定一个 N 叉树，返回其节点值的前序遍历。
例如，给定一个 3叉树 :
返回其前序遍历: [1,3,5,6,2,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?
示例
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4090 访问。
public class Program {
public static void Main(string[] args) {
var root = new Node(1,
new List<Node> {
new Node(3, new List<Node> {
new Node(5, null),
new Node(6, null)
}),
new Node(2, null),
new Node(4, null)
});
var res = Preorder(root);
ShowArray(res);
res = Preorder2(root);
ShowArray(res);
Console.ReadKey();
}
private static void ShowArray(IList<int> array) {
foreach(var num in array) {
Console.Write($"{num} ");
}
Console.WriteLine();
}
public static IList<int> Preorder(Node root) {
var list = new List<int>();
Pre(root, ref list);
return list;
}
public static void Pre(Node root, ref List<int> list) {
if(root == null) return;
list.Add(root.val);
if(root.children == null) return;
foreach(var child in root.children) {
Pre(child, ref list);
}
return;
}
public static IList<int> Preorder2(Node root) {
var list = new List<int>();
if(root == null) return list;
var stack = new Stack<Node>();
stack.Push(root);
while(stack.Any()) {
var pop = stack.Pop();
list.Add(pop.val);
if(pop.children != null) {
for(var i = pop.children.Count() - 1; i >= 0; i--)
stack.Push(pop.children[i]);
}
}
return list;
}
public class Node {
public int val;
public IList<Node> children;
public Node() { }
public Node(int _val, IList<Node> _children) {
val = _val;
children = _children;
}
}
}以上给出2种算法实现，以下是这个案例的输出结果：
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4090 访问。
1 3 5 6 2 4
1 3 5 6 2 4分析：
显而易见，以上2种算法的时间复杂度均为： 。