C#LeetCode刷题之#559-N叉树的最大深度​​​​​​​(Maximum Depth of N-ary Tree)

C#LeetCode刷题之#559-N叉树的最大深度​​​​​​​(Maximum Depth of N-ary Tree)

问题

给定一个 N 叉树,找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如,给定一个 3叉树 :

C#LeetCode刷题之#559-N叉树的最大深度​​​​​​​(Maximum Depth of N-ary Tree)

我们应返回其最大深度,3。

说明:

  • 树的深度不会超过 1000。
  • 树的节点总不会超过 5000。

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, given a 3-ary tree:

We should return its max depth, which is 3.

Note:

  • The depth of the tree is at most 1000.
  • The total number of nodes is at most 5000.

示例

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, new List<Node>()),
                    new Node(6, new List<Node>())
            }),
            new Node(2, new List<Node>()),
            new Node(4, new List<Node>())
          });

        var res = MaxDepth(root);
        Console.WriteLine(res);

        res = MaxDepth2(root);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    public static int MaxDepth(Node root) {
        if(root == null) return 0;
        var res = 1;
        Depth(root, 1, ref res);
        return res;
    }

    public static void Depth(Node root, int depth, ref int max) {
        if(root.children == null || root.children.Count == 0) {
            max = Math.Max(max, depth);
            return;
        }
        foreach(var child in root.children) {
            Depth(child, depth + 1, ref max);
        }
    }

    public static int MaxDepth2(Node root) {
        if(root == null) return 0;
        var res = 0;
        if(root.children != null && root.children.Count != 0) {
            foreach(var child in root.children) {
                var depth = MaxDepth2(child);
                res = Math.Max(res, depth);
            }
        }
        return res + 1;
    }

    public class Node {
        public int val;
        public IList<Node> children;
        public Node() { }
        public Node(int _val, IList<Node> _children) {
            val = _val;
            children = _children;
        }
    }

}

以上给出2种算法实现,以下是这个案例的输出结果:

3
3

分析

显而易见,以上2种算法的时间复杂度均为: O(n)​ 。

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

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

发表评论

登录后才能评论