Easy

题目描述

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

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

Nary-Tree input serialization 是用层序遍历，每组子节点都由 null 值分割（参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：3

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5

提示：

  • 节点总数在范围 [0, 10^4] 内。
  • N 叉树的深度小于或等于 1000 。

解题思路

这道题要求计算N叉树的最大深度，本质上是一个树的遍历问题。我们可以用两种经典方法来解决：

方法一：深度优先搜索（DFS） 递归地计算每个子树的最大深度，然后取其中的最大值加1。对于空节点返回0，对于叶子节点返回1。时间复杂度为O(n)，空间复杂度为O(h)，其中h是树的高度。

方法二：广度优先搜索（BFS） 使用队列进行层序遍历，每遍历完一层就将深度加1。当队列为空时，说明所有节点都已遍历完毕，此时的深度就是最大深度。时间复杂度为O(n)，空间复杂度为O(w)，其中w是树的最大宽度。

两种方法的时间复杂度相同，但DFS的实现更加简洁直观，而BFS在某些情况下可能有更好的空间表现。推荐使用DFS递归方法，代码简洁且易于理解。

推荐解法：深度优先搜索（DFS）

代码实现

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == nullptr) {
            return 0;
        }
        
        int maxChildDepth = 0;
        for (Node* child : root->children) {
            maxChildDepth = max(maxChildDepth, maxDepth(child));
        }
        
        return maxChildDepth + 1;
    }
};

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        
        if not root.children:
            return 1
        
        return max(self.maxDepth(child) for child in root.children) + 1

public class Solution {
    public int MaxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        
        int maxChildDepth = 0;
        foreach (Node child in root.children) {
            maxChildDepth = Math.Max(maxChildDepth, MaxDepth(child));
        }
        
        return maxChildDepth + 1;
    }
}

var maxDepth = function(root) {
    if (!root) return 0;
    
    if (!root.children || root.children.length === 0) return 1;
    
    let maxChildDepth = 0;
    for (let child of root.children) {
        maxChildDepth = Math.max(maxChildDepth, maxDepth(child));
    }
    
    return 1 + maxChildDepth;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型DFS方法BFS方法
时间复杂度O(n)O(n)
空间复杂度O(h)O(w)

其中 n 是节点总数，h 是树的高度，w 是树的最大宽度。在最坏情况下，h = n（退化为链表），w = n（完全展开的树）。

相关题目