题目
给定一棵 N 叉树的根节点 root
,计算这棵树的直径长度。
N 叉树的直径指的是树中任意两个节点间路径中 最长 路径的长度。这条路径可能经过根节点,也可能不经过根节点。
(N 叉树的输入序列以层序遍历的形式给出,每组子节点用 null 分隔)
示例 1:
输入:root = [1,null,3,2,4,null,5,6]
输出:3
解释:直径如图中红线所示。
示例 2:
输入:root = [1,null,2,null,3,4,null,5,null,6]
输出:4
示例 3:
输入: 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]
输出: 7
提示:
- N 叉树的深度小于或等于
1000
。 - 节点的总个数在
[0, 10^4]
间。
解题
方法一:递归 DFS
思路
由题意可以把树的直径长度看作 ,就可以把问题 “计算这棵树的直径长度” 转换为 “找到某个‘有两个高度最高的子树的高度加起来是最大的’的节点”,例如:
如图该二叉树的直径可以看作两个黄色区域的子树的高度和+2。
具体做法是:遍历每一个节点,把它所有子树的高度计算出来放入集合,找出最高的两个高度,把它们加起来与当前树的直径作比较,维护一个最大的值。
又因为 $$一颗树的高度=max(所有子树的高度) + 1$$,所以可以使用深度优先遍历完成:
- 遍历到某个节点,如果该节点是叶子节点,直接返回高度
0
。 - 否则,定义一个集合用于存放子树高度(
depthList
)。 - 遍历子节点集合,把每个子节点作为根节点递归地求高度,并放入
depthList
。 - 遍历
depthList
,把最高的两个高度拿出来(max
,secMax
)。 - 如果
max + secMax
比ans
大就更新ans
。 - 返回 作为该树的高度。
代码
class Solution {
private int ans = 0;
public int diameter(Node root) {
if (root == null) return 0;
dfs(root);
return ans;
}
private int dfs(Node root) {
if (root.children == null) return 0;
List<Integer> depthList = new ArrayList<>();
for (Node child : root.children) {
depthList.add(dfs(child));
}
int max = 0, secMax = 0;
for (int depth : depthList) {
if (depth > max) {
secMax = max;
max = depth;
} else if (depth > secMax) {
secMax = depth;
}
}
ans = Math.max(ans, max + secMax);
return max + 1;
}
}
优化
在遍历子节点列表时同时维护最大子树高度和次大子树高度。
class Solution {
private int ans = 0;
public int diameter(Node root) {
if (root == null) return 0;
dfs(root);
return ans;
}
private int dfs(Node root) {
int maxDepth = 0;
for (Node child : root.children) {
int secMaxDepth = dfs(child);
ans = Math.max(ans, maxDepth + secMaxDepth);
maxDepth = Math.max(maxDepth, secMaxDepth);
}
return maxDepth + 1;
}
}
评论区