盘丝洞破阵寻珠2026 华为OD机试真题 6月24日华为OD上机新系统考试真题 100 分题型点击查看华为 OD 机试真题完整目录2026最新华为OD机试新系统卷 双机位C卷 真题题库目录全覆盖题库 逐点算法考点详解题目描述天命人深入盘丝洞洞内布满了蜘蛛精设下的迷阵。整座洞穴呈二叉树结构每个结点是一间石室石室中藏有灵气结晶整数可正可负零值视为非负。天命人从根石室出发寻找通往叶子石室的路径收集灵气。但盘丝洞有毒瘴禁制路径上不允许出现连续两个或以上灵气值为负的石室。叶子石室的定义左右子结点均为空的结点。请实现一个函数在一遍遍历中同时计算以下三个指标合法路径的最大灵气和是否存在合法路径和 ≥ 给定阈值合法路径的总数2026 华为OD机试真题 6月24日华为OD上机新系统考试真题 100 分题型输入描述二叉树根节点 root整数 threshold输出描述包含 3 个整数的数组 [max_val, has_path_ge, count]max_val合法路径的最大灵气和无合法路径返回 −2147483648has_path_ge存在合法路径和 ≥threshold 返回 1否则返回 0count合法路径的总数二叉树输入格式说明二叉树采用层次遍历方式序列化表示按从上到下、从左到右的顺序依次列出每个节点的值# 表示该位置为空节点无子节点空树用 {} 或 {#} 表示示例{10,−5,20,#,8,−6,15} 表示解析规则根节点为 10左子节点 −5其左子为空 #右子为 8右子节点 20左子 −6右子 15。数据范围项目范围节点数0≤n≤105节点值−100≤val≤100树深度≤104阈值−109≤threshold≤109空树说明当 n0 时返回 [−2147483648,0,0]。示例1输入10,-5,20,#,8,-6,1540输出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,#,#,1018输出18,1,1说明二叉树结构从根到叶子仅 1 条路径5→−3→8→−2→10和 18负节点 −3 与 −2 之间隔了正节点 8不连续路径合法。最大合法路径和 18存在路径和 ≥18合法路径数 1。解题思路核心思想DFS 深度优先搜索遍历所有从根到叶子的路径记录合法路径的相关统计。关键约束 - 路径上不允许出现连续两个负节点- 零值视为非负不触发约束状态追踪 -cur_sum当前路径的累计和 -prev_neg前一个节点是否为负用于判断连续负节点剪枝条件 - 当遇到负节点且前一个节点也为负时剪枝路径非法算法步骤解析输入的二叉树层序遍历DFS 从根节点出发 - 当前节点为负且前一个节点也为负 → 剪枝 - 否则更新cur_sum- 到达叶子节点 → 更新max_val、has_ge、count- 递归处理左右子节点返回结果数组复杂度分析时间复杂度O(n)每个节点最多访问一次空间复杂度O(h)h 为树高递