一、题目描述
给定一个 N 叉树,找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
例如,给定一个
3叉树
:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5CM2MDNzczYyEWNlJjM2ITNzYzXwETMxcTMxIzLcBTMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
我们应返回其最大深度,3。
说明:
- 树的深度不会超过
。1000
- 树的节点总不会超过
。5000
二、思路
采用深度优先搜索,递归获取子节点的最大深度,接着更新maxRootDepth即可。
该方案的时间复杂度为O(N),N代表节点总数,空间复杂度为O(1)。
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
if (root.children == null) {
return 1;
}
int rootMaxDepth = 0;
for (Node children : root.children) {
//递归获取子节点的最大深度
int childrenMaxDepth = maxDepth(children);
//更新max值
rootMaxDepth = Math.max(rootMaxDepth, childrenMaxDepth);
}
return rootMaxDepth + 1;
}