本文详解 leetcode 2467「树中最高盈利路径」的算法逻辑，并重点指出 javascript 实现中因动态数组长度判断导致的层序遍历错误，提供修复方案与完整可运行代码。
本文详解 leetcode 2467「树中最高盈利路径」的算法逻辑，并重点指出 javascript 实现中因动态数组长度判断导致的层序遍历错误，提供修复方案与完整可运行代码。
LeetCode 2467 要求在无向树中模拟 Alice 从节点 0 出发、Bob 从给定节点 bob 出发同时向根节点 0 移动的过程，计算 Alice 沿任意根到叶路径所能获得的最大净收益。关键约束在于：若 Alice 与 Bob 同时到达同一节点，该节点金额减半；若 Bob 先到达（即更早抵达），Alice 到达时收益为 0；否则 Alice 获得全额金额。
算法分为两步：
-
预处理 Bob 的路径：通过 DFS 找出 Bob 从起点到根节点
0的唯一路径，并记录每个节点在该路径中的到达步数（深度），存入哈希表step； -
BFS 模拟 Alice 的所有可能路径：从节点
0开始层序遍历，对每个扩展节点neighbor，根据当前depth + 1（Alice 到达该节点的步数）与step[neighbor]（Bob 到达该节点的步数）的关系，决定收益：depth + 1 或 <code>neighbor不在 Bob 路径中 → 全额amount[neighbor]；-
depth + 1 === step[neighbor]→ 半额Math.floor(amount[neighbor] / 2)； -
depth + 1 > step[neighbor]→ 收益为0。
⚠️ 关键陷阱（导致 JS 版本失败的根本原因）：
Python 原版使用 for _ in range(len(que)) 固定遍历当前层节点数，而原始 JS 代码写成：
for (let j = 0; j < queue.length; j++) {
let [cur, parent, profit] = queue.shift();
// ... 推入新节点 queue.push(...)
}由于 queue.length 在每次循环条件判断时动态更新（shift() 减少、push() 增加），导致内层循环实际遍历的节点数远超预期，破坏了层序结构——Alice 的“深度”depth 不再准确对应其所在层级，进而使 depth + 1 与 step[neighbor] 的比较失效，最终低估收益（如失败用例中输出 16435，期望 17590）。
✅ 正确修复方式：在循环开始前缓存当前层节点数量：
const levelSize = queue.length;
for (let j = 0; j < levelSize; j++) {
let [cur, parent, profit] = queue.shift();
// ... 正常处理，queue.push() 不影响本次循环次数
}或使用倒序计数（更简洁）：
for (let j = queue.length; j > 0; j--) {
let [cur, parent, profit] = queue.shift();
// ...
}以下是修复后的完整 JavaScript 解决方案（已通过全部测试用例，包括问题中提供的失败用例）：
/**
* @param {number[][]} edges
* @param {number} bob
* @param {number[]} amount
* @return {number}
*/
var mostProfitablePath = function(edges, bob, amount) {
const n = amount.length;
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
// DFS to find Bob's path to node 0
let bobPath = null;
const dfs = (node, parent, path) => {
if (node === 0) {
bobPath = [...path];
return true;
}
for (const neighbor of graph[node]) {
if (neighbor === parent) continue;
path.push(neighbor);
if (dfs(neighbor, node, path)) return true;
path.pop();
}
return false;
};
dfs(bob, -1, [bob]);
// Map: node -> Bob's arrival step
const step = {};
for (let i = 0; i < bobPath.length; i++) {
step[bobPath[i]] = i;
}
// BFS for Alice starting from node 0
let ans = -Infinity;
const iniProfit = (bob === 0) ? Math.floor(amount[0] / 2) : amount[0];
let queue = [[0, -1, iniProfit]]; // [node, parent, profit]
let depth = 0;
while (queue.length > 0) {
const levelSize = queue.length; // ✅ Critical fix: freeze current level size
for (let j = 0; j < levelSize; j++) {
const [cur, parent, profit] = queue.shift();
// Leaf node (except root): update answer
if (cur !== 0 && graph[cur].length === 1) {
ans = Math.max(ans, profit);
}
// Explore neighbors
for (const neighbor of graph[cur]) {
if (neighbor === parent) continue;
let newProfit;
if (!step.hasOwnProperty(neighbor) || depth + 1 < step[neighbor]) {
newProfit = amount[neighbor];
} else if (depth + 1 === step[neighbor]) {
newProfit = Math.floor(amount[neighbor] / 2);
} else {
newProfit = 0;
}
queue.push([neighbor, cur, profit + newProfit]);
}
}
depth++;
}
return ans;
};? 补充说明：
- Bob 的 DFS 必须保证找到唯一最短路径（树中两点间路径唯一），因此无需额外剪枝；
- Alice 的 BFS 使用
graph[cur].length === 1 && cur !== 0判断叶子节点是安全的（根节点0度数可能为 1，但非叶子）； - 整数除法统一使用
Math.floor(x / 2)，确保负数（如-9152）也向下取整，符合题意（如-9152 / 2 = -4576）； - 时间复杂度：O(n)，空间复杂度：O(n)，满足大规模输入要求。
掌握层序遍历中“冻结队列长度”这一细节，是避免 BFS 类题目逻辑错误的关键。
