0559. Maximum Depth of N-ary Tree¶
题目信息¶
- 题号:
0559
- 难度:
Easy
- 主题:
N 叉树、根到叶路径、节点层数、空树
- 原题:
- 重点:
深度按根到最远叶节点的节点数量计算、根深度为 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)。