2026 华为OD机试真题 6月24日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

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

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

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

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

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

2026 华为OD机试真题 6月24日华为OD上机新系统考试真题 100 分题型

输入描述

二叉树根节点 root，整数 threshold

输出描述

包含 3 个整数的数组 [max_val, has_path_ge, count]：

• max_val：合法路径的最大灵气和，无合法路径返回 −2147483648
• has_path_ge：存在合法路径和 ≥threshold 返回 1，否则返回 0
• 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

说明

从根到叶子共 33 条路径：

从根到叶子共 3 条路径：

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

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

示例2

输入

-5,-3,#,#,-7
-100

输出

-2147483648,0,0

说明

二叉树结构：

从根到叶子仅 1 条路径：

• −5→−3→−7，和 = −15，但 −5 与 −3 为连续负节点，路径非法。

示例3

输入

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

输出

18,1,1

说明

二叉树结构：

从根到叶子仅 1 条路径：

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

最大合法路径和 = 18，存在路径和 ≥18，合法路径数 = 1。

解题思路

核心思想

DFS 深度优先搜索：遍历所有从根到叶子的路径，记录合法路径的相关统计。

关键约束：

• 路径上不允许出现连续两个负节点
• 零值视为非负，不触发约束

状态追踪：

• cur_sum：当前路径的累计和
• prev_neg：前一个节点是否为负（用于判断连续负节点）

剪枝条件：

• 当遇到负节点且前一个节点也为负时，剪枝（路径非法）

算法步骤

1. 解析输入的二叉树（层序遍历）
2. DFS 从根节点出发：
   • 当前节点为负且前一个节点也为负 → 剪枝
   • 否则更新 cur_sum
   • 到达叶子节点 → 更新 max_val、has_ge、count
   • 递归处理左右子节点
3. 返回结果数组

复杂度分析

• 时间复杂度：O(n)，每个节点最多访问一次
• 空间复杂度：O(h)，h 为树高（递