
问题
给定一个 N 叉树,返回其节点值的后序遍历。
例如,给定一个 3叉树
:
返回其后序遍历: [5,6,3,2,4,1]
.
说明: 递归法很简单,你可以使用迭代法完成此题吗?
Given an n-ary tree, return the postorder traversal of its nodes’ values.
For example, given a 3-ary
tree:
Return its postorder traversal as: [5,6,3,2,4,1]
.
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 = Postorder(root); ShowArray(res); res = Postorder2(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> Postorder(Node root) { var list = new List<int>(); Post(root, ref list); return list; } public static void Post(Node root, ref List<int> list) { if(root == null) return; if(root.children == null) { list.Add(root.val); return; } foreach(var child in root.children) { Post(child, ref list); } list.Add(root.val); return; } public static IList<int> Postorder2(Node root) { if(root == null) return new List<int>(); var list = new List<int>(); if(root.children != null) { foreach(var node in root.children) { list.AddRange(Postorder2(node)); } } list.Add(root.val); 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种算法实现,以下是这个案例的输出结果:
5 6 3 2 4 1 5 6 3 2 4 1
分析:
显而易见,以上2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4092。