LeetCode - N叉树的最大深度

晓痴

发布于 2019-07-24 14:08:32

5920

发布于 2019-07-24 14:08:32

文章被收录于专栏：曌的晓痴

今天很开心的收到了阿里的offer邮件。

这题是LeetCode第559题，求N叉树的最大深度，难度为简单，两月以前的做的一题。

原题地址：https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/

题目描述：

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

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

例如，给定一个 3叉树 :

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

说明:

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这题的思路很清晰，递归。

首先遍历根节点的每个子节点，每个子节点的初始深度都为1。
在遍历每个子节点时，都将深度加1，再次遍历子节点的每个子树，获取子树中深度最深的深度。

中文官网题解：

https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/solution/

个人题解：

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
   public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        if (root.children == null || root.children.isEmpty()) {
            return 1;
        }
        int max = 0;
        for (Node node : root.children) {
            int m = maxDepth(node, 1);
            if (m > max) {
                max = m;
            }
        }
        return max;
    }

    public int maxDepth(Node root, int current) {
        if (root == null) {
            return current;
        }
        if (root.children == null || root.children.isEmpty()) {
            return current + 1;
        }
        int max = 0;
        for (Node node : root.children) {
            int m = maxDepth(node, current);
            if (m > max) {
                max = m;
            }
        }
        return current + max;
    }
}

结果：

啊哈，又是正常水平的一题。