
本文详解geeksforgeeks经典题“sum of nodes on the longest path from root to leaf node”的解法,重点剖析因共享可变对象导致的逻辑错误,并提供线程安全、无副作用的递归实现。
本文详解geeksforgeeks经典题“sum of nodes on the longest path from root to leaf node”的解法,重点剖析因共享可变对象导致的逻辑错误,并提供线程安全、无副作用的递归实现。
在解决二叉树根到叶最长路径节点和问题时,核心目标是:找到从根节点到任意叶子节点的路径中,长度(节点数)最长的一条;若存在多条等长路径,则选取其中节点值总和最大的那条,并返回该路径上所有节点值之和。
原代码看似逻辑清晰——用 Info 类封装路径长度(count)与路径和(sum),并通过递归比较左右子树结果来决策。但关键缺陷在于:复用同一个 ans 对象作为参数并反复修改,导致左右子树的递归调用相互污染。
具体表现为:
- 所有递归层级共用一个
ans实例; -
findSum(root.left, ans)和findSum(root.right, ans)并非独立计算,而是先后覆写同一内存地址; - 因此
l和r实际引用的是同一对象(最终状态为右子树更新后的值),丧失了左右子树结果的独立性; - 这直接破坏了“比较左右最优路径”这一逻辑前提,造成结果错误(如示例中输出 12 而非正确值 13)。
✅ 正确做法是:让每次递归调用都返回一个全新的 Info 对象,避免状态共享。 基础情况(空节点)应主动创建新实例,递归返回值天然独立,再由当前层统一裁决哪条路径更优。
以下是修正后的完整实现:
class Solution {
static class Info {
int count; // 当前路径节点数
int sum; // 当前路径节点值之和
Info(int count, int sum) {
this.count = count;
this.sum = sum;
}
}
public Info findSum(Node root) {
// 基础情况:空节点,返回长度0、和0的新对象
if (root == null) {
return new Info(0, 0);
}
// 递归获取左右子树的最优路径信息(各自独立对象)
Info left = findSum(root.left);
Info right = findSum(root.right);
// 决策规则:优先比长度,长度相同时比和
Info best = left;
if (right.count > left.count ||
(right.count == left.count && right.sum > left.sum)) {
best = right;
}
// 将当前节点加入最优路径:长度+1,和累加
best.count++;
best.sum += root.data;
return best;
}
public int sumOfLongRootToLeafPath(Node root) {
if (root == null) return 0;
return findSum(root).sum;
}
}
? 关键改进点总结:
- ✅ 消除副作用:移除可变入参
ans,完全依赖返回值传递状态; - ✅ 保证独立性:每个
Info实例均为新创建,左右子树结果互不干扰; - ✅ 明确决策逻辑:使用
right.count > left.count || (equal && right.sum > left.sum)精确实现题目要求的“先比长度、再比和”优先级; - ✅ 边界鲁棒:
null节点返回(0, 0),天然适配叶子节点(其左右均为null,取max(0,0)后count=1,sum=root.data)。
该方案时间复杂度为 $O(N)$(遍历每个节点一次),空间复杂度为 $O(H)$(递归栈深度,$H$ 为树高),符合工程实践标准,且逻辑清晰、易于验证与扩展。










