0559. Maximum Depth of N-ary Tree

题目信息

题号:

0559

难度:

Easy

主题:

N 叉树、根到叶路径、节点层数、空树

原题:

LeetCode 0559

重点:

深度按根到最远叶节点的节点数量计算、根深度为 1、空树深度为 0

题目重述

给定一棵 N 叉树的根节点 root,返回树的最大深度。最大深度是从根节点到任意叶节点的最长路径所包含的节点数量。

若树为空,返回 0;非空树的根节点深度为 1。每个节点可以拥有零个或多个子节点,叶节点是没有子节点的节点。

自建示例

最深路径位于某个孙辈分支:

输入:根 1 的孩子为 [2,3],3 的孩子为 [4,5],5 的孩子为 [6]
输出:4
解释:最长根到叶路径为 1 -> 3 -> 5 -> 6,共包含 4 个节点。

空树:

输入:root = null
输出:0
解释:没有任何节点,因此最大深度为 0。

递归取最深孩子路径

空节点深度为 0;非空节点的深度是 1 加上所有孩子深度的最大值。叶节点没有孩子,最大孩子深度取 0,因此返回 1。

C++ 实现

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

代码分析

每个节点只需知道最深孩子的结果,递归返回值与根到叶的节点计数定义一致。时间复杂度为 O(n),递归栈空间为 O(h)。