本文详解 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 <p>由于 <code>queue.length</code> 在每次循环条件判断时<strong>动态更新</strong>（<code>shift()</code> 减少、<code>push()</code> 增加），导致内层循环实际遍历的节点数远超预期，破坏了层序结构——Alice 的“深度”<code>depth</code> 不再准确对应其所在层级，进而使 <code>depth + 1</code> 与 <code>step[neighbor]</code> 的比较失效，最终低估收益（如失败用例中输出 <code>16435</code>，期望 <code>17590</code>）。</p><p>✅ <strong>正确修复方式</strong>：在循环开始前缓存当前层节点数量：</p><pre class="brush:php;toolbar:false;">const levelSize = queue.length;
for (let j = 0; j <p>或使用倒序计数（更简洁）：</p><pre class="brush:php;toolbar:false;">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 0) {
const levelSize = queue.length; // ✅ Critical fix: freeze current level size
for (let j = 0; j <p>? <strong>补充说明</strong>：</p>
- 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 类题目逻辑错误的关键。
