给定一个二叉树,您需要计算树的直径长度。树的直径是树上任意两个节点之间最长路径的长度。这条路径可能穿过根节点。 实现函数diameterOfBinaryTree(TreeNode root),返回树的直径长度。java代码实现
时间: 2024-03-17 18:41:34 浏览: 57
好的,以下是 Java 代码实现:
```
class Solution {
private int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
calculateDiameter(root);
return maxDiameter;
}
private int calculateDiameter(TreeNode node) {
if (node == null) {
return 0;
}
int leftDepth = calculateDiameter(node.left);
int rightDepth = calculateDiameter(node.right);
maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
return Math.max(leftDepth, rightDepth) + 1;
}
}
```
其中,`maxDiameter` 用于记录当前已经求出的最大直径长度。`calculateDiameter` 方法用于递归计算每个节点的最长路径长度和子树直径长度。在递归过程中,我们使用另一个变量 `depth` 记录当前节点的深度,最后返回的是以当前节点为路径的最长路径长度。在递归过程中,我们还需要不停地更新 `maxDiameter`。
阅读全文