C++如何实现二叉树的最大路径和计算（从叶子到叶子）-C++-PHP中文网

“从叶子到叶子”的最大路径和是指二叉树中任意两叶子节点间经其最近公共祖先的简单路径上节点值之和的最大值；它要求两端必须为叶子、路径不重复边，本质是带权树直径问题，不能直接复用maxpathsum因后者不要求端点为叶子且未校验路径终点类型。

c++如何实现二叉树的最大路径和计算（从叶子到叶子）

什么是“从叶子到叶子”的最大路径和

这指的是二叉树中任意两个叶子节点之间路径上所有节点值（含两端叶子）的和的最大值。注意：路径必须经过它们的最近公共祖先（LCA），且不能重复经过边——也就是传统意义上的简单路径，不是向下单向路径（如 maxPathSum 常见变种中“从根出发”的那种）。它本质上是树的直径问题在带权节点下的推广。

为什么不能直接复用 LeetCode 的 `maxPathSum` 解法

LeetCode 第124题的 maxPathSum 求的是“任意节点出发、可向上折返”的最大路径和，允许路径只包含一个方向（比如左→根→右），但它的定义不要求两端都是叶子。如果强行把原解法拿来用，会漏掉约束条件，也可能把非叶子节点当端点计入结果。

原解法中 maxSinglePath 返回的是“从当前节点向下能走的最大单边路径”，但没检查终点是否为叶子
若某路径一端是内部节点（非叶子），它不满足“叶子到叶子”要求，必须排除
需要额外判断：递归返回时，只有真正到达叶子的路径才参与拼接；中间节点只能作为LCA被用来合并左右子树的叶子路径

如何改造 DFS 实现叶子到叶子的路径和

核心思路是：对每个节点，维护两个信息——
① 以该节点为起点、向下走到某个叶子的最大路径和（记作 downToLeaf）；
② 在其子树内已找到的、完全位于该子树内的最大叶子间路径和（记作 bestInSubtree）。

关键改造点：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

叶子节点：downToLeaf = node->val，bestInSubtree = node->val（单点路径也算“叶子到叶子”，长度为1）
非叶子节点：若左右子树都存在，则可能形成跨子树路径：left.downToLeaf + right.downToLeaf + node->val；否则只能继承某一边的 bestInSubtree
downToLeaf 只有在至少一个子树存在叶子路径时才更新，否则设为负无穷（表示无法从该节点走到叶子）
注意空指针处理：若某子节点为空，对应 downToLeaf 不参与计算，bestInSubtree 取另一侧值

示例片段（简化版）：

struct Result {
    int downToLeaf;      // 从当前节点出发，向下到某叶子的最大和（必须终止于叶子）
    int bestInSubtree;   // 当前子树内已知的最大叶子-叶子路径和
};
Result dfs(TreeNode* root) {
    if (!root) return {INT_MIN, INT_MIN};
    if (!root->left && !root->right) {
        return {root->val, root->val}; // 叶子：单点即路径
    }
    Result l = dfs(root->left);
    Result r = dfs(root->right);
    int cross = INT_MIN;
    if (l.downToLeaf != INT_MIN && r.downToLeaf != INT_MIN) {
        cross = l.downToLeaf + r.downToLeaf + root->val;
    }
    int best = max({l.bestInSubtree, r.bestInSubtree, cross});
    int down = max(l.downToLeaf, r.downToLeaf) + root->val;
    return {down, best};
}