华为 · 树 · 算法编程题
华为 时限 3 秒 / 256 MB

题目描述

在一片神秘的荧光森林中,生长着一种名为“辉光之树”的奇特植物。
这些植物的根系在地底深处交织成一张巨大的网络,形成了一棵宏伟的二叉树结构。
每株植物都是树上的一个节点,并且自身储存着一定的能量。
作为一名探索这片森林的植物学家,您发现当能量以一种特定的“之字形”模式在植物间传导时,会引发壮观的“能量共鸣”现象。
您的任务是找出这片森林中所有可能形成的、总能量值恰好等于特定值的共鸣路径。
给定一个由 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 。

样例共 2 组

样例 1
输入
10
3 2 1 2 1 4 1 -1 -1 5
8
输出
2
样例 2
输入
3
2 3 1
4
输出
-1

算法解析依据一般

考点:树

限制 3 秒 / 256MB | 标准输入输出

题目画像

  • 元素值域:E ≤ 1e4,N_nodes ≤ 1024(注意整数类型选择,避免溢出)
  • 源站时限:3 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:树

树结构上的遍历(DFS 求子树信息 / BFS 求层序),多数树题是「后序遍历 + 回溯」。

思路框架(树 通法 · 非本题专属)

  1. 按输入建图(父子关系一般给父节点编号,孩子用邻接表存)。
  2. 确定遍历方式:自底向上合并子树信息(后序 DFS)或自顶向下传参(前序 DFS)。
  3. 对每个节点,用孩子的答案合并出当前节点的答案。
  4. 涉及层间操作(如层序变换)时用 BFS 逐层处理。

实现要点:递归深度可能到 1e5,注意递归爆栈;必要时改迭代或调整递归深度。

复杂度:时间 O(n) | 空间 O(n)

该范式的通法易错点

  • 递归深度过大导致爆栈。
  • 建树时父子关系方向搞反(把树当成有向图但遍历方向错)。

对照本题

  • 元素值域最大到 1e4 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例

样例 1

  • 输入:10 / 3 2 1 2 1 4 1 -1 -1 5 / 8
  • 输出:2

样例 2

  • 输入:3 / 2 3 1 / 4
  • 输出:-1

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2025年秋招-华为-11月05号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解