LeetCode 559. N 叉树的最大深度

约 5 分钟
文章信息 9 个分类 5 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 5-10 字节跳动 美团 腾讯
标签
深度优先搜索 树 广度优先搜索 层序遍历 二叉树经典题
目录

题目描述

✅ 559. N 叉树的最大深度

image-20230312171608549

image-20230312171605492

题意分析

给定一棵每个节点可以有任意多个孩子的树，要求返回根节点到最远叶子节点这条路径上的节点个数。题目对两个端点情形给了明确约定：空树的深度是 0，只有一个根节点的树深度是 1。

「节点数」而不是「边数」是必须抠清楚的一处措辞。按边计数时，单节点树的深度是 0；按节点计数时是 1。两种口径相差恰好 1，而这个 1 正是递归返回时那次加法的来源，弄反了会让所有答案整体偏移。

与二叉树版本相比，唯一的结构差异是孩子数量不固定：不再是固定的左右两个指针，而是一个长度可变的孩子列表。这意味着「取所有子树中的最大值」不能写成两项取大，而要写成对列表的一轮归约。

边界情形：根为空；根存在但孩子列表为空（即叶子）；孩子列表存在但某个元素为空指针；树退化成一条长链导致深度接近节点总数。最后一种情形对递归实现意味着调用栈可能很深，是需要在面试中主动提及的风险点。

解法：递归深度优先搜索

核心思路

一棵非空 N 叉树的最大深度，等于所有子树最大深度中的最大值再加 1；空树深度为 0。这个定义可以直接写成递归。

递归函数 maxDepth(node) 的语义是“返回以 node 为根的子树深度”。先递归得到每个孩子子树的深度，保留最大值，最后加上当前节点这一层。

正确性可按树高归纳：叶子没有孩子，循环中的最大值保持 0，返回 1；若每个孩子都能正确返回自身深度，那么其中最大者就是从当前节点向下的最长路径，增加当前层后得到当前子树的最大深度。

N 叉树与二叉树的区别只在于孩子数量不固定，因此把“比较左右子树”改成“遍历孩子列表”，递归框架不变。

解题步骤

  • 若根节点为空，返回 0。
  • 初始化 childMax = 0。
  • 遍历当前节点的所有孩子，递归计算其深度。
  • 用每个返回值更新 childMax。
  • 返回 childMax + 1，其中 1 代表当前节点这一层。

例如根的三个孩子子树深度分别为 1、3、2，则根的最大深度为 max(1, 3, 2) + 1 = 4。

代码实现

class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }

        int childMax = 0;
        for (Node child : root.children) {
            childMax = Math.max(childMax, maxDepth(child));
        }
        return childMax + 1;
    }
}

func maxDepth(root *Node) int {
    if root == nil {
        return 0
    }

    childMax := 0
    for _, child := range root.Children {
        depth := maxDepth(child)
        if depth > childMax {
            childMax = depth
        }
    }
    return childMax + 1
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点只访问一次，每条父子边只遍历一次。
  • 空间复杂度：$O(h)$，其中 $h$ 是树高，来自递归调用栈；最坏链状结构为 $O(n)$，较平衡时通常更低。

关键点总结

  • 递归返回值必须定义清楚：这里返回“当前子树的最大深度”。
  • 状态转移是“孩子深度最大值 + 当前层”，不是孩子深度之和。
  • 空树返回 0，叶子节点自然返回 1，无需额外判断叶子。
  • 递归空间取决于树高而不是节点总数，最坏情况下两者相等。

易错点总结

  • 空树返回 1，会让所有非空树的答案整体多一层。
  • 对孩子深度求和，会计算多个分支的节点层数，而不是最长根到叶路径。
  • 忘记在最大孩子深度上加 1，会漏掉当前节点。
  • 只处理第一个孩子，等价于把 N 叉树误当成链表，可能错过更深分支。
  • 把额外空间一律写成 $O(\log n)$；N 叉树也可能退化成长度为 $n$ 的单链。
  • 实际数据结构若允许 children == null，Java 需先判空；LeetCode 给出的节点孩子列表按题目约定使用。

相似题目

题目 难度 考察点
104. 二叉树的最大深度 简单 孩子固定为两个，合并写成左右取大
剑指 Offer 55 - I. 二叉树的深度 简单 与 104 同题换编号，可对照递归与层序两种写法
111. 二叉树的最小深度 简单 取最小值时必须排除空子树，否则单侧链会算错
110. 平衡二叉树 简单 在求高度的同时判断左右差值，需自底向上剪枝
剑指 Offer 55 - II. 平衡二叉树 简单 与 110 同题，练习用返回值兼表高度与失衡标记
面试题 04.04. 检查平衡性 简单 同为平衡判定，接口与命名略有不同
543. 二叉树的直径 简单 答案是跨越节点的路径，需在递归中另记全局最值
429. N 叉树的层序遍历 中等 同为多叉树，要求逐层输出而不只是层数