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

📝 核心笔记：二叉树的直径 (Diameter of Binary Tree)

1. 核心思想 (一句话总结)

“每个节点都做两件事：1. 试图把左右臂展连起来挑战世界纪录；2. 挑一只长手臂伸向长官汇报。”

• 直径不一定经过根节点：它可能完全出现在左子树或右子树内部。
• 转化问题：直径 = 某一个节点处的(左子树最大链长 + 右子树最大链长)的最大值。
• 我们利用后序遍历，在回溯的过程中，算出以当前节点为“拐点”的最长路径，并不断更新全局最大值。

2. 您的“边数计算”逻辑 (return -1)

这是一个非常棒的细节：

• Null 节点：返回-1。
• 叶子节点：左 (-1) + 1 = 0，右 (-1) + 1 = 0。链长为 0。正确（叶子没边）。
• 中间节点：假设左子树高L，右子树高R。

• • lLen = L + 1(连上左边那条边)。
  • rLen = R + 1(连上右边那条边)。
  • 这种写法直接把+1分摊到了每一层递归里，非常优雅。

🔍 代码回忆清单

// 题目：LC 543. Diameter of Binary Tree class Solution { // 1. 全局变量：记录遍历过程中遇到的"最大臂展" // 类似于打擂台，谁的 (左+右) 更长，谁就当老大 private int ans; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return ans; } // 返回值含义：从当前节点向下，能延伸出的【最大单边链长】(边数) private int dfs(TreeNode node) { // 2. Base Case: 巧妙的 -1 // 既然我们算的是"边数"，null 节点贡献 -1， // 这样它的父节点 (叶子) 加上 1 之后刚好是 0 if (node == null) { return -1; } // 3. 后序遍历：先拿到左右的情报 int lLen = dfs(node.left) + 1; // 左边最长链 + 连接左子树的那条边 int rLen = dfs(node.right) + 1; // 右边最长链 + 连接右子树的那条边 // 4. 更新全局最大直径 (Hook) // 假设路径经过当前节点 (穿过)，那长度就是 左 + 右 ans = Math.max(ans, lLen + rLen); // 5. 向上汇报 // 只能选一条最长的路继续往上延伸 (不能分叉) return Math.max(lLen, rLen); } }

⚡ 快速复习 CheckList (易错点)

• [ ]为什么不能直接 returnlLen + rLen？

• • 这是初学者最容易犯的错。
  • dfs函数的职责是“向上汇报高度”。如果返回lLen + rLen，相当于告诉父节点“我是一条分叉的线”，但路径是不能分叉的。父节点只能接你的左手或右手。
  • 只有在更新全局ans时，才考虑“分叉/拐弯”的情况。

• [ ]直径通过根节点吗？

• • 不一定。
  • 比如树的左边特别深，像个大哑铃，直径可能就在左子树内部。所以必须用全局变量ans在遍历过程中实时抓取最大值。

• [ ]时间复杂度？

• • 每个节点遍历一次。

🖼️ 数字演练

树结构：

1 / \ 2 3 / \ 4 5

1. Node 4 (Leaf):

• • dfs(null)returns -1.
  • lLen= -1+1=0,rLen= -1+1=0.
  • ans= max(0, 0+0) = 0.
  • Return: 0.

1. Node 5 (Leaf):

• • Return: 0.

1. Node 2:

• • lLen(from 4) = 0 + 1 = 1.
  • rLen(from 5) = 0 + 1 = 1.
  • ans= max(0, 1+1) =2. (路径 4-2-5)
  • Return: max(1, 1) = 1. (告诉 1 号节点，我这边最长能提供 1 条边的深度)

1. Node 3 (Leaf):

• • Return: 0.

1. Node 1 (Root):

• • lLen(from 2) = 1 + 1 = 2.
  • rLen(from 3) = 0 + 1 = 1.
  • ans= max(2, 2+1) =3. (路径 4-2-1-3)
  • Return: 2.

最终结果: 3。