← 返回编程题库
coding-prob-of-reaching-target-leaves中等免费版50ms未尝试

二叉情景树上击中目标叶集合的概率

Probability of Reaching a Target Leaf Set on a Binary Scenario Tree

开始编码

题目类型

算法 · Graph算法 · Tree量化 · Pricing量化 · Statistics适配身份 · Quant Developer
题目描述样例编码区结果

输入是一棵以两组平行子节点 index 数组形式给出的二叉情景树，长度均为 N，根节点 index 为 0：left_child[i] 与 right_child[i] 是节点 i 两个孩子的 index（-1 表示该侧无孩子），up_prob[i] 是从内部节点 i 走向 left_child[i] 的概率（向右的概率为 1 - up_prob[i]）。节点是叶节点，当且仅当 left_child[i] == -1 AND right_child[i] == -1 同时成立；非叶节点必有两个孩子（树良构）。注意：数组顺序不要求为层序——只要满足上述父子关系，孩子可以位于 [0, N-1] 内任何非根 index。target_leaf_indices 是所有叶节点 index 的一个子集，刻画目标吸收集合。

实现 solution(left_child: list[int], right_child: list[int], up_prob: list[float], target_leaf_indices: list[int]) -> float，返回从根节点（index 0）出发，按 up_prob 在每个内部节点随机分叉的行走者，最终落在目标叶集合中某个叶节点的概率：

prob_reach[v]={1.0v 是目标集合中的叶0.0v 是不在目标集合中的叶up_prob[v]⋅prob_reach[left_child[v]]+(1−up_prob[v])⋅prob_reach[right_child[v]]其它情形 \text{prob\_reach}[v] = \begin{cases} 1.0 & v \text{ 是目标集合中的叶} \\ 0.0 & v \text{ 是不在目标集合中的叶} \\ \text{up\_prob}[v] \cdot \text{prob\_reach}[\text{left\_child}[v]] + (1 - \text{up\_prob}[v]) \cdot \text{prob\_reach}[\text{right\_child}[v]] & \text{其它情形} \end{cases}

返回 prob_reach[0] 作为单个 float。最自然的实现形态是一遍 DFS 后序递归，时间 O(N)，递归栈 O(\text{depth})。在递归之前把 target_leaf_indices 一次性转成 Python set，使叶节点成员判定为 O(1)。

边界情形。若 N == 1（根本身就是唯一叶），返回 1.0（若 0 在 target_leaf_indices 中）否则 0.0。若 target_leaf_indices 为空，答案为 0.0。若 target_leaf_indices 包含所有叶节点，答案严格为 1.0——行走必落在某处。因为非叶节点必有两个孩子，N 个节点上能达到的最深形态是交替"内部-叶 stub"的退化链，深度约为 (N-1)/2（N = 4000 时约 2000），仍会超出 Python 默认 1000 的递归上限；参考解法防御性地调用 sys.setrecursionlimit（写成显式迭代后序也接受）。比较器使用绝对容差 1e-9。

例

solution(
    left_child  = [1, 3, 5, -1, -1, -1, -1],
    right_child = [2, 4, 6, -1, -1, -1, -1],
    up_prob     = [0.6, 0.7, 0.2, 0.0, 0.0, 0.0, 0.0],
    target_leaf_indices = [3, 6]
)

返回 0.74。这是一棵深度 2 的二叉树：根 0 以 0.6 走向左孩子 1、以 0.4 走向右孩子 2。节点 1 以 0.7 走向叶 3（目标，值 1.0）、以 0.3 走向叶 4（非目标，0.0）；节点 2 以 0.2 走向叶 5（非目标，0.0）、以 0.8 走向叶 6（目标，1.0）。后序递推：prob_reach[1] = 0.7 * 1.0 + 0.3 * 0.0 = 0.7；prob_reach[2] = 0.2 * 0.0 + 0.8 * 1.0 = 0.8；prob_reach[0] = 0.6 * 0.7 + 0.4 * 0.8 = 0.42 + 0.32 = 0.74。路径求和的对照计算一致：目标叶 3（路径概率 0.6 * 0.7 = 0.42）与目标叶 6（路径概率 0.4 * 0.8 = 0.32）相加为 0.74。非目标叶 4、5 贡献为零，四个叶节点的路径概率合计 1.0。

朴素的"逐叶向上回溯"枚举对每个叶要重新走 depth 个祖先，最坏复杂度为 O(L * depth)，退化链形态可退化至 O(N^2)，在 N = 4000 上开始吃力；后序 DFS 每个节点恰好访问一次为 O(N)，50 ms 时间预算下非常宽裕。

实践背景

二叉情景树在量化研究的角落里随处可见：单标的的 CRR / Jarrow-Rudd 二叉树、随机游走在粗化状态空间上的离散实现、信用迁移树、远期利率演化的多期子树。"行走击中目标叶集合的概率"回答的是一种基础的奇异定价原语——路径无条件地落入某组指定"触发"事件中任何一个的概率（例如：到期时策略 in-the-money、OR 在某终端日期上敲入障碍被穿越、OR 信用评级最终落在违约状态）。它在操作上明显区别于期望收益的回溯（按 pnl 加权叶节点，输出价格），区别于最差叶行走（仅 min 结构，忽略概率），也区别于美式回溯归纳（每个节点 max(intrinsic, continuation)）——同样的 DFS 骨架，三种不同的递推。判定当前任务该用哪种递推，是这类问题的核心思辨。

约束条件

  • 1 <= N <= 4000，其中 N == len(left_child) == len(right_child) == len(up_prob)。
  • left_child[i] 与 right_child[i] 要么为 -1（无该侧孩子），要么为 [0, N-1] 内的合法 index；节点是叶节点当且仅当两者都为 -1，否则两个孩子都存在（树良构，每个非根 index 在某个父节点的孩子位置上恰好出现一次）。
  • 对所有 v，0.0 <= up_prob[v] <= 1.0；up_prob 在叶节点上被忽略。
  • target_leaf_indices 是一个由互不相同的节点 index 组成的列表，每个 index 都是树中的叶节点（数量在 0 到所有叶节点之间，无重复）。
  • 输出是单个 Python float，落在 [0.0, 1.0]；比较器为浮点比较，绝对容差 1e-9。答案是一个概率，而不是期望，不是计数，不是路径。

样例

Case 1 · statement-example: depth-2 binary tree, two target leaves at corners

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0.6,0.7,0.2,0,0,0,0],[3,6]]

期望: 0.74

根 0 以 0.6/0.4 分叉到节点 1/2；节点 1 以 0.7 走向叶 3（目标），节点 2 以 0.8 走向叶 6（目标）。命中概率 = 0.6*0.7 + 0.4*0.8 = 0.74。

Case 2 · typical: depth-2 tree, single target on inner-left leaf

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0.6,0.7,0.2,0,0,0,0],[4]]

期望: 0.18000000000000002

目标只为叶 4（路径 0.6 * 0.3 = 0.18）。

Case 3 · typical: depth-3 full binary, uniform 0.5 splits, every-other target leaf

输入: [[1,3,5,7,9,11,13,-1,-1,-1,-1,-1,-1,-1,-1],[2,4,6,8,10,12,14,-1,-1,-1,-1,-1,-1,-1,-1],[0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5],[7,9,11,13]]

期望: 0.5

深度 3 全二叉，所有 up_prob=0.5；每条根到叶路径概率 1/8，4 个目标叶 -> 0.5。

Case 4 · typical: target contains every leaf returns exactly 1.0

输入: [[1,3,5,7,9,11,13,-1,-1,-1,-1,-1,-1,-1,-1],[2,4,6,8,10,12,14,-1,-1,-1,-1,-1,-1,-1,-1],[0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3],[7,8,9,10,11,12,13,14]]

期望: 1

所有叶都为目标，无论 up_prob 取值，递推恒等于 1.0。

Case 5 · typical: empty target returns exactly 0.0

输入: [[1,3,5,7,9,11,13,-1,-1,-1,-1,-1,-1,-1,-1],[2,4,6,8,10,12,14,-1,-1,-1,-1,-1,-1,-1,-1],[0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4],[]]

期望: 0

目标集合为空，所有叶贡献 0.0，根返回 0.0。

Case 6 · typical: target covers entire left subtree

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0.7,0.3,0.9,0,0,0,0],[3,4]]

期望: 0.7

目标恰为节点 1 之下的所有叶 -> prob_reach[1]=1.0；prob_reach[0]=0.7。

Case 7 · typical: depth-3 with biased upper-level probabilities, two target leaves

输入: [[1,3,5,7,9,11,13,-1,-1,-1,-1,-1,-1,-1,-1],[2,4,6,8,10,12,14,-1,-1,-1,-1,-1,-1,-1,-1],[0.8,0.6,0.4,0.5,0.5,0.5,0.5,0,0,0,0,0,0,0,0],[7,10]]

期望: 0.4

目标是叶 7 与叶 10；后序递推得到根的命中概率。

Case 8 · typical: random binary tree with 6 internals, three target leaves

输入: [[1,3,7,5,-1,-1,-1,9,11,-1,-1,-1,-1],[2,4,8,6,-1,-1,-1,10,12,-1,-1,-1,-1],[0.4722,0.3796,0.21,0.4879,0.8933,0.3898,0.6074,0.7672,0.6958,0.2663,0.8018,0.5912,0.1022],[4,6,11]]

期望: 0.6748674897520001

随机二叉树，6 个内部节点，3 个目标叶。

Case 9 · boundary: N=1 root-is-leaf, root in target -> 1.0

输入: [[-1],[-1],[0],[0]]

期望: 1

N=1，唯一节点是叶且 0 在目标集合中，返回 1.0。

Case 10 · boundary: N=1 root-is-leaf, target empty -> 0.0

输入: [[-1],[-1],[0],[]]

期望: 0

N=1，目标为空，返回 0.0。

Case 11 · boundary: N=3 up_prob=0.0 forces right branch, left target ignored

输入: [[1,-1,-1],[2,-1,-1],[0,0,0],[1]]

期望: 0

up_prob=0.0 把所有概率给到右孩子；目标为左叶 1，命中概率 0.0。

Case 12 · boundary: N=3 up_prob=1.0 forces left branch, left target hits -> 1.0

输入: [[1,-1,-1],[2,-1,-1],[1,0,0],[1]]

期望: 1

up_prob=1.0 把所有概率给到左孩子；目标为左叶 1，命中概率 1.0。

Case 13 · boundary: N=3 target covers both leaves -> 1.0

输入: [[1,-1,-1],[2,-1,-1],[0.37,0,0],[1,2]]

期望: 1

目标 = {1, 2} 是全部叶，命中概率恒为 1.0。

Case 14 · boundary: N=3 empty target -> 0.0

输入: [[1,-1,-1],[2,-1,-1],[0.5,0,0],[]]

期望: 0

目标集合为空，根返回 0.0。

Case 15 · boundary: depth-2 deterministic walk reaching exactly one corner leaf

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0,0,0,0,0,0,0],[6]]

期望: 1

所有 up_prob=0.0，行走必然到达节点 6，命中概率 1.0。

Case 16 · boundary: depth-2 deterministic walk misses target -> 0.0

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0,0,0,0,0,0,0],[3]]

期望: 0

所有 up_prob=0.0，行走到节点 6 而非节点 3，命中概率 0.0。

Case 17 · boundary: depth-2 always-left walk hits leftmost leaf

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[1,1,1,1,1,1,1],[3]]

期望: 1

所有 up_prob=1.0，行走必沿左侧到索引 3，命中概率 1.0。

Case 18 · boundary: depth-2 uniform 0.5 splits, single target leaf -> 0.25

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0.5,0.5,0.5,0.5,0.5,0.5,0.5],[3]]

期望: 0.25

深度 2，所有 up_prob=0.5；每个叶概率 0.25，目标只一个叶 -> 0.25。

Case 19 · boundary: N=1 ignores up_prob value, target covers root -> 1.0

输入: [[-1],[-1],[0.5],[0]]

期望: 1

N=1，up_prob 任取（叶节点上忽略），0 在目标 -> 返回 1.0。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例；服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出；点击「提交评测」会进入隐藏测试。

Case 1 · statement-example: depth-2 binary tree, two target leaves at corners

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0.6,0.7,0.2,0,0,0,0],[3,6]]

期望: 0.74

根 0 以 0.6/0.4 分叉到节点 1/2；节点 1 以 0.7 走向叶 3（目标），节点 2 以 0.8 走向叶 6（目标）。命中概率 = 0.6*0.7 + 0.4*0.8 = 0.74。

Case 2 · typical: depth-2 tree, single target on inner-left leaf

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0.6,0.7,0.2,0,0,0,0],[4]]

期望: 0.18000000000000002

目标只为叶 4（路径 0.6 * 0.3 = 0.18）。

Case 3 · typical: depth-3 full binary, uniform 0.5 splits, every-other target leaf

输入: [[1,3,5,7,9,11,13,-1,-1,-1,-1,-1,-1,-1,-1],[2,4,6,8,10,12,14,-1,-1,-1,-1,-1,-1,-1,-1],[0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5],[7,9,11,13]]

期望: 0.5

深度 3 全二叉，所有 up_prob=0.5；每条根到叶路径概率 1/8，4 个目标叶 -> 0.5。

Case 4 · typical: target contains every leaf returns exactly 1.0

输入: [[1,3,5,7,9,11,13,-1,-1,-1,-1,-1,-1,-1,-1],[2,4,6,8,10,12,14,-1,-1,-1,-1,-1,-1,-1,-1],[0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3],[7,8,9,10,11,12,13,14]]

期望: 1

所有叶都为目标，无论 up_prob 取值，递推恒等于 1.0。

Case 5 · typical: empty target returns exactly 0.0

输入: [[1,3,5,7,9,11,13,-1,-1,-1,-1,-1,-1,-1,-1],[2,4,6,8,10,12,14,-1,-1,-1,-1,-1,-1,-1,-1],[0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4],[]]

期望: 0

目标集合为空，所有叶贡献 0.0，根返回 0.0。

Case 6 · typical: target covers entire left subtree

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0.7,0.3,0.9,0,0,0,0],[3,4]]

期望: 0.7

目标恰为节点 1 之下的所有叶 -> prob_reach[1]=1.0；prob_reach[0]=0.7。

Case 7 · typical: depth-3 with biased upper-level probabilities, two target leaves

输入: [[1,3,5,7,9,11,13,-1,-1,-1,-1,-1,-1,-1,-1],[2,4,6,8,10,12,14,-1,-1,-1,-1,-1,-1,-1,-1],[0.8,0.6,0.4,0.5,0.5,0.5,0.5,0,0,0,0,0,0,0,0],[7,10]]

期望: 0.4

目标是叶 7 与叶 10；后序递推得到根的命中概率。

Case 8 · typical: random binary tree with 6 internals, three target leaves

输入: [[1,3,7,5,-1,-1,-1,9,11,-1,-1,-1,-1],[2,4,8,6,-1,-1,-1,10,12,-1,-1,-1,-1],[0.4722,0.3796,0.21,0.4879,0.8933,0.3898,0.6074,0.7672,0.6958,0.2663,0.8018,0.5912,0.1022],[4,6,11]]

期望: 0.6748674897520001

随机二叉树，6 个内部节点，3 个目标叶。

Case 9 · boundary: N=1 root-is-leaf, root in target -> 1.0

输入: [[-1],[-1],[0],[0]]

期望: 1

N=1，唯一节点是叶且 0 在目标集合中，返回 1.0。

Case 10 · boundary: N=1 root-is-leaf, target empty -> 0.0

输入: [[-1],[-1],[0],[]]

期望: 0

N=1，目标为空，返回 0.0。

Case 11 · boundary: N=3 up_prob=0.0 forces right branch, left target ignored

输入: [[1,-1,-1],[2,-1,-1],[0,0,0],[1]]

期望: 0

up_prob=0.0 把所有概率给到右孩子；目标为左叶 1，命中概率 0.0。

Case 12 · boundary: N=3 up_prob=1.0 forces left branch, left target hits -> 1.0

输入: [[1,-1,-1],[2,-1,-1],[1,0,0],[1]]

期望: 1

up_prob=1.0 把所有概率给到左孩子；目标为左叶 1，命中概率 1.0。

Case 13 · boundary: N=3 target covers both leaves -> 1.0

输入: [[1,-1,-1],[2,-1,-1],[0.37,0,0],[1,2]]

期望: 1

目标 = {1, 2} 是全部叶，命中概率恒为 1.0。

Case 14 · boundary: N=3 empty target -> 0.0

输入: [[1,-1,-1],[2,-1,-1],[0.5,0,0],[]]

期望: 0

目标集合为空，根返回 0.0。

Case 15 · boundary: depth-2 deterministic walk reaching exactly one corner leaf

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0,0,0,0,0,0,0],[6]]

期望: 1

所有 up_prob=0.0，行走必然到达节点 6，命中概率 1.0。

Case 16 · boundary: depth-2 deterministic walk misses target -> 0.0

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0,0,0,0,0,0,0],[3]]

期望: 0

所有 up_prob=0.0，行走到节点 6 而非节点 3，命中概率 0.0。

Case 17 · boundary: depth-2 always-left walk hits leftmost leaf

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[1,1,1,1,1,1,1],[3]]

期望: 1

所有 up_prob=1.0，行走必沿左侧到索引 3，命中概率 1.0。

Case 18 · boundary: depth-2 uniform 0.5 splits, single target leaf -> 0.25

输入: [[1,3,5,-1,-1,-1,-1],[2,4,6,-1,-1,-1,-1],[0.5,0.5,0.5,0.5,0.5,0.5,0.5],[3]]

期望: 0.25

深度 2，所有 up_prob=0.5；每个叶概率 0.25，目标只一个叶 -> 0.25。

Case 19 · boundary: N=1 ignores up_prob value, target covers root -> 1.0

输入: [[-1],[-1],[0.5],[0]]

期望: 1

N=1，up_prob 任取（叶节点上忽略），0 在目标 -> 返回 1.0。