当前位置：首页 > news >正文

完整教程：【Leetcode hot 100】543.二叉树的直径

news 2025/9/15 14:14:15

完整教程：【Leetcode hot 100】543.二叉树的直径

问题链接

543.二叉树的直径

问题描述

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

示例 1：
在这里插入图片描述

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

输入：root = [1,2]
输出：1

提示：

树中节点数目在范围 [1, 104] 内
-100 <= Node.val <= 100

问题解答

解题思路

核心观察：二叉树的直径 = 某个节点的左子树深度 + 右子树深度（路径以该节点为中心，左右延伸）。
深度优先搜索（DFS）：通过 DFS 计算每个节点的子树深度时，同步记录“当前节点的左右子树深度之和”，并更新全局最大直径。
边界处理：若树为空（根节点为 null），直径为 0；若树只有一个节点，直径也为 0（无边）。

Java 代码实现

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution
{
public int diameterOfBinaryTree(TreeNode root) {
// 用数组存储最大直径（Java 中基本类型无法在递归中修改，数组是引用类型）
int[] maxDiameter = {
0
};
// 调用 DFS 计算深度，同时更新最大直径
calculateDepth(root, maxDiameter);
return maxDiameter[0];
}
/**
* 计算当前节点的子树深度，并同步更新最大直径
* @param node 当前节点
* @param maxDiameter 存储最大直径的数组（引用传递）
* @return 当前节点的子树深度（以当前节点为根的树的深度）
*/
private int calculateDepth(TreeNode node, int[] maxDiameter) {
// 递归终止条件：空节点深度为 0
if (node == null) {
return 0;
}
// 递归计算左子树深度
int leftDepth = calculateDepth(node.left, maxDiameter);
// 递归计算右子树深度
int rightDepth = calculateDepth(node.right, maxDiameter);
// 更新最大直径：当前节点的左右子树深度之和可能是新的最大值
maxDiameter[0] = Math.max(maxDiameter[0], leftDepth + rightDepth);
// 返回当前节点的子树深度：1（当前节点自身） + 左右子树的最大深度
return 1 + Math.max(leftDepth, rightDepth);
}
}

代码解释

递归函数 calculateDepth：
- 作用：既计算当前节点的子树深度，又在计算过程中更新全局最大直径。
- 终止条件：空节点的深度为 0（node == null 时返回 0）。
- 核心逻辑：
  - 先递归计算左、右子树的深度（leftDepth 和 rightDepth）。
  - 用 leftDepth + rightDepth 计算当前节点的“左右子树深度之和”，并与 maxDiameter[0] 比较，更新最大直径。
  - 返回当前节点的子树深度：1 + Math.max(leftDepth, rightDepth)（1 代表当前节点自身，加上左右子树的最大深度）。
为什么用数组存储 maxDiameter：
Java 是值传递，若用 int 基本类型，递归函数中修改的值无法传递到外部。用数组（长度为 1）存储，数组是引用类型，递归中修改数组元素会直接影响外部。