二叉树直径是任意两节点间最长路径的边数，未必经过根；不能仅用左右子树高度相加，因最大直径可能完全位于左或右子树内，需后序遍历中同时维护深度与局部直径。
二叉树直径到底是什么，为什么不能直接用左右子树高度相加
二叉树的直径定义为任意两个节点之间最长路径的边数（不是节点数），这条路径不一定经过根节点。很多人第一反应是 left_height + right_height，但这是错的——那只适用于「经过当前根」的路径；真正的直径可能是完全落在左子树或右子树内部的一条路径。
所以必须在递归过程中同时维护两个信息：以当前节点为起点向下的最大深度（用于父节点计算），以及以当前节点为路径最高点时的局部直径（用于全局更新）。
用 DFS 一次遍历完成，避免重复计算高度
核心思路是后序遍历：先算左右子树各自的最大深度和子树内的最大直径，再合并。关键在于，每个节点只访问一次，height 和 diameter 都从子树返回值推导，不额外调用求高函数。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 定义递归函数
std::pair<int int></int>：first 是以当前节点为根的子树最大深度（边数），second 是该子树内的最大直径 - 空节点返回
{-1, 0}（深度为 -1，这样叶子节点深度才是 0，符合边数定义） - 当前节点的深度 =
1 + std::max(left_depth, right_depth) - 当前节点作为“最高点”的路径长度 =
left_depth + right_depth + 2（+2 是连接左右两段的两条边） - 当前子树直径 =
std::max({left_diam, right_diam, left_depth + right_depth + 2})
示例片段（简化版）：
std::pair<int, int> dfs(TreeNode* root) {
if (!root) return {-1, 0};
auto [l_dep, l_diam] = dfs(root->left);
auto [r_dep, r_diam] = dfs(root->right);
int dep = 1 + std::max(l_dep, r_dep);
int diam = std::max({l_diam, r_diam, l_dep + r_dep + 2});
return {dep, diam};
}
LeetCode 543 常见错误：把直径当节点数、空节点深度设为 0
LeetCode 543 明确要求返回「边的数量」，但很多人误按节点数理解，导致结果多 1。另一个高频坑是空节点返回 {0, 0}，这样叶子节点深度变成 1，最终直径会多算 2 条边。
验证方式：
- 单节点树：直径应为 0 → 若返回 1，说明用了节点数逻辑
- 两层满二叉树（根 + 左右子）：直径应为 2（左→根→右），对应边数
- 若测试用例
[1,2,3,4,5]输出 3，说明正确（路径 4→2→1→3，共 3 条边）
想节省空间？用引用传参替代 pair 返回
如果不想用 std::pair 或结构体，可以用一个引用参数记录全局最大直径，主函数只返回深度。这更贴近经典写法，也省去构造临时对象的开销。
要点：
- 函数签名改为
int dfs(TreeNode* root, int& max_diam) - 每次算完左右深度后，立刻更新
max_diam = std::max(max_diam, l_dep + r_dep + 2) - 返回值仅为深度，不再携带直径信息
- 注意：
max_diam必须是引用，否则各层更新互不影响
这种写法在面试中更常见，也更容易解释清楚状态传递逻辑。
真正容易被忽略的是：直径路径可能完全避开根，所以任何只算根处 left + right 的代码都必然漏解；而深度的基准（空节点为 -1 还是 0）一旦定错，整棵树的边数就会系统性偏移。
