盘丝洞灵气路径

题目描述

整座洞穴呈二叉树结构，每个结点是一间石室，石室中藏有灵气结晶（整数，可正可负，零值视为非负）。

天命人从根石室出发，寻找通往叶子石室的路径收集灵气。但盘丝洞有毒瘴禁制：路径上不允许出现连续两个或以上灵气值为负的石室。

叶子石室的定义：左右子结点均为空的结点。

请实现一个函数，在一遍遍历中同时计算以下三个指标：

1. 合法路径的最大灵气和
2. 是否存在合法路径和 ≥ 给定阈值
3. 合法路径的总数

数据范围：

• 节点数 0 ≤ n ≤ 10⁵
• 节点值 -100 ≤ val ≤ 100
• 树深度 ≤ 10⁴
• 阈值 -10⁹ ≤ threshold ≤ 10⁹
• 空树（n=0）返回 [-2147483648, 0, 0]

示例

输入： {10,-5,20,#,8,-6,15},40

二叉树结构：

        10
       /  \
     -5   20
       \  / \
       8 -6 15

输出： [45,1,3]

说明： 从根到叶子共 3 条路径：

• 10 → -5 → 8，和 = 13，负节点不连续，合法
• 10 → 20 → -6，和 = 24，负节点不连续，合法
• 10 → 20 → 15，和 = 45，无负节点，合法

最大合法路径和 = 45，存在路径和 ≥ 40 → 1，合法路径数 = 3。

解题思路

核心思路：DFS 递归，维护连续负节点计数

从根开始 DFS，递归传递三个状态：

• curSum：当前路径累加和
• negCount：当前路径连续负节点的个数

递归规则：

1. 累加当前节点的值
2. 若当前节点值为负，negCount++；否则 negCount = 0
3. 若 negCount >= 2，立即剪枝（禁制触发，此路径非法）
4. 若到达叶子节点（无左右子节点），统计结果
5. 否则继续向左右子节点递归

迭代解法（栈模拟DFS）： 用显式栈替代递归，避免深层递归导致的栈溢出问题。栈中每个元素保存 [node, curSum, negCount]。

代码实现

function pathCal(root, threshold) {
    if (!root) return [-2147483648, 0, 0];

    let maxVal = -Infinity;
    let pathCount = 0;
    let hasGe = 0;

    function dfs(node, curSum, negCount) {
        curSum += node.val;

        if (node.val < 0) {
            negCount++;
        } else {
            negCount = 0;
        }

        // 禁制触发：连续两个负节点，剪枝
        if (negCount >= 2) return;

        // 到达叶子节点，统计结果
        if (!node.left && !node.right) {
            pathCount++;
            if (curSum > maxVal) maxVal = curSum;
            if (curSum >= threshold) hasGe = 1;
            return;
        }

        if (node.left) dfs(node.left, curSum, negCount);
        if (node.right) dfs(node.right, curSum, negCount);
    }

    dfs(root, 0, 0);
    return [maxVal === -Infinity ? -2147483648 : maxVal, hasGe, pathCount];
}

/**
 * 迭代版（栈模拟DFS），避免深层递归栈溢出
 */
function pathCalStack(root, threshold) {
    if (!root) return [-2147483648, 0, 0];

    let maxVal = -Infinity;
    let pathCount = 0;
    let hasGe = 0;

    const stack = [[root, 0, 0]];

    while (stack.length) {
        const [node, parentSum, parentNeg] = stack.pop();
        const curSum = parentSum + node.val;
        const negCount = node.val < 0 ? parentNeg + 1 : 0;

        if (negCount >= 2) continue;

        if (!node.left && !node.right) {
            pathCount++;
            if (curSum > maxVal) maxVal = curSum;
            if (curSum >= threshold) hasGe = 1;
            continue;
        }

        if (node.right) stack.push([node.right, curSum, negCount]);
        if (node.left) stack.push([node.left, curSum, negCount]);
    }

    return [maxVal === -Infinity ? -2147483648 : maxVal, hasGe, pathCount];
}

复杂度分析

• 时间复杂度： O(n)，每个节点最多访问一次，剪枝操作可减少无效路径的探索。
• 空间复杂度： O(h)，其中 h 为树的高度。递归版为调用栈深度，迭代版为显式栈大小。h ≤ 10⁴。

{10,-5,20,#,8,-6,15},40

[45,1,3]