#LeetCode刷题之#589-N叉树的前序遍C历(N-ary Tree Preorder Traversal)

#LeetCode刷题之#589-N叉树的前序遍C历(N-ary Tree Preorder Traversal)

问题

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

例如,给定一个 3叉树 :

#LeetCode刷题之#589-N叉树的前序遍C历(N-ary Tree Preorder Traversal)

返回其前序遍历: [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种算法的时间复杂度均为: O(n)​ 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4090

发表评论

登录后才能评论