
问题
给定一个 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?
示例
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种算法实现,以下是这个案例的输出结果:
1 3 5 6 2 4 1 3 5 6 2 4
分析:
显而易见,以上2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4090。