题目内容

天命人深入盘丝洞，洞内布满了蜘蛛精设下的迷阵。整座洞穴呈二叉树结构，每个结点是一间石室，石室中藏有灵气结晶（整数，可正可负，零值视为非负）。

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

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

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

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

输入描述

二叉树根节点 $\text{root}$，整数 $\text{threshold}$

输出描述

包含 $3$ 个整数的数组 $[\text{max\_val}$, $\text{has\_path\_ge}$, $\text{count}]$：

• $\text{max\_val}$：合法路径的最大灵气和，无合法路径返回 $-2147483648$
• $\text{has\_path\_ge}$：存在合法路径和 $\ge \text{threshold}$ 返回 $1$，否则返回 $0$
• $\text{count}$：合法路径的总数

二叉树输入格式说明

二叉树采用层次遍历方式序列化表示：

• 按从上到下、从左到右的顺序依次列出每个节点的值
• $\#$ 表示该位置为空节点（无子节点）
• 空树用 $\{\}$ 或 $\{\#\}$ 表示

示例：$\{10,-5,20,\#,8,-6,15\}$ 表示：

解析规则：根节点为 $10$，左子节点 $-5$（其左子为空 $\#$，右子为 $8$），右子节点 $20$（左子 $-6$，右子 $15$）。

数据范围

空树说明：当 $n = 0$ 时返回 $[-2147483648, 0, 0]$。

样例1

输入

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

输出

[45,1,3]

说明

二叉树结构：

从根到叶子共 $3$ 条路径：

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

最大合法路径和 = $45$，存在路径和 $\ge 40$，合法路径数 = $3$。

样例2

输入

{-5,-3,#,#,-7},-100

输出

[-2147483648,0,0]

说明

二叉树结构：

从根到叶子仅 $1$ 条路径：

• $-5 \to -3 \to -7$，和 = $-15$，但 $-5$ 与 $-3$ 为连续负节点，路径非法。

样例3

输入

{5,-3,#,#,8,-2,#,#,10},18

输出

[18,1,1]

说明

二叉树结构：

从根到叶子仅 $1$ 条路径：

• $5 \to -3 \to 8 \to -2 \to 10$，和 = $18$，负节点 $-3$ 与 $-2$ 之间隔了正节点 $8$，不连续，路径合法。

最大合法路径和 = $18$，存在路径和 $\ge 18$，合法路径数 = $1$。