在一片神秘的荧光森林中,生长着一种名为“辉光之树”的奇特植物。 这些植物的根系在地底深处交织成一张巨大的网络,形成了一棵宏伟的二叉树结构。 每株植物都是树上的一个节点,并且自身储存着一定的能量。 作为一名探索这片森林的植物学家,您发现当能量以一种特定的“之字形”模式在植物间传导时,会引发壮观的“能量共鸣”现象。 您的任务是找出这片森林中所有可能形成的、总能量值恰好等于特定值的共鸣路径。 给定一个由 N 株荧光植物构成的二叉树,以及一个目标能量值 E 。您需要计算出满足以下条件的 共鸣路径 的总数量。 路径 (Path) : 一条有效的路径必须从树中的任意一个节点开始,并一直延伸到某个 叶子节点(没有子节点的植物)结束。 共鸣路径 (Resonance Path) : 一条路径要被称为“共鸣路径”,其上的节点序列必须遵循“之字形”的能量传导规则,并且路径长度至少为3。规则如下: 1. 从父节点到第一个子节点的方向是任意的(左或右)。 2. 此后,能量的传导方向必须严格交替。即,如果上一步是“父 -> 左子”,则下一步必须是“当前 -> 右子”;如果上一步是“父 -> 右子”,则下一步必须是“当前 -> 左子”。 * 例如:`父 -> 左子 -> 右子 -> 左子 -> ... -> 叶子节点` * 或者:`父 -> 右子 -> 左子 -> 右子 -> ... -> 叶子节点` 任务目标 : 找出所有满足“路径上所有植物的能量值之和等于目标能量 E ”的 共鸣路径 的数量。
第一行 : 一个整数 N_nodes ,表示辉光之树的节点总数。 ( 1 ≤ N_nodes ≤ 1024 ) 第二行 : 一个包含 N_nodes 个整数的数组 V 。 V_i 代表二叉树中第 i 个节点(植物)的能量值。 能量值 V_i ≥ 0 。 若某个位置的值为 -1 ,表示该节点在树的结构中不存在。 建树规则 : 数组 V 是树的层序遍历表示。例如, V_0 是根节点, V_1, V_2 分别是根的左右子节点, V_3, V_4, V_5, V_6 是下一层的节点,以此类推。 第三行 : 一个整数 E ,代表目标能量和。 ( 0 ≤ E ≤ 10000 )
输出一个整数,表示路径能量和恰好为 E 的共鸣路径总数。 如果不存在任何共鸣路径(例如,树的深度不足以形成长度为3的路径),则输出 -1 。
10 3 2 1 2 1 4 1 -1 -1 5 8
2
3 2 3 1 4
-1
考点:树
限制 3 秒 / 256MB | 标准输入输出
参考方向:树
树结构上的遍历(DFS 求子树信息 / BFS 求层序),多数树题是「后序遍历 + 回溯」。
思路框架(树 通法 · 非本题专属)
实现要点:递归深度可能到 1e5,注意递归爆栈;必要时改迭代或调整递归深度。
复杂度:时间 O(n) | 空间 O(n)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1
10 / 3 2 1 2 1 4 1 -1 -1 5 / 82样例 2
3 / 2 3 1 / 4-1解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2025年秋招-华为-11月05号开发岗。