C++如何实现二叉树的直径计算-C++-PHP中文网

二叉树直径是任意两节点间最长路径的边数，未必经过根；不能仅用左右子树高度相加，因最大直径可能完全位于左或右子树内，需后序遍历中同时维护深度与局部直径。

c++如何实现二叉树的直径计算

二叉树直径到底是什么，为什么不能直接用左右子树高度相加

二叉树的直径定义为任意两个节点之间最长路径的边数（不是节点数），这条路径不一定经过根节点。很多人第一反应是 left_height + right_height，但这是错的——那只适用于「经过当前根」的路径；真正的直径可能是完全落在左子树或右子树内部的一条路径。

所以必须在递归过程中同时维护两个信息：以当前节点为起点向下的最大深度（用于父节点计算），以及以当前节点为路径最高点时的局部直径（用于全局更新）。

用 DFS 一次遍历完成，避免重复计算高度

核心思路是后序遍历：先算左右子树各自的最大深度和子树内的最大直径，再合并。关键在于，每个节点只访问一次，height 和 diameter 都从子树返回值推导，不额外调用求高函数。

实操建议：

定义递归函数 std::pair：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};
}
</int>