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

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

题目描述

给定一棵完全二叉树的层序遍历序列（用逗号分隔的节点值字符串表示），以及两个目标节点值 frm 和 to，求这两个节点之间的最小跳数（即最短路径经过的边数）。

完全二叉树的性质：

• 根节点索引为 0
• 索引为 i 的节点的父节点索引为 (i-1) // 2
• 索引为 i 的节点的左子节点索引为 2*i + 1
• 索引为 i 的节点的右子节点索引为 2*i + 2

注意：如果目标节点不存在于树中，或者 frm 和 to 相同，返回 -1 或 0（特殊情况见用例）。

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

输入描述

第一行：字符串形式的层序遍历序列，节点值用逗号分隔，例如 1,2,3,4,5,6,7

第二行：起始节点值 frm

第三行：目标节点值 to

输出描述

输出一个整数，表示从 frm 到 to 的最小跳数（即最短路径的边数）。

• 如果节点不存在，返回 -1
• 如果 frm == to，返回 0

示例1

输入

1,2,3
2
3

输出

2

说明

二叉树结构：

    1
   / \
  2   3

从节点 2 到节点 3，需要经过边：2 -> 1 -> 3，共 2 跳。

示例2

输入

1,2,3,4,5,6,7
4
5

输出

2

说明

二叉树结构：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

节点 4 和节点 5 是兄弟节点，都位于节点 2 下方，最小跳数为 2（4 -> 2 -> 5）。

解题思路

核心思想

利用完全二叉树的数组表示特性，通过计算两个节点的深度和最近公共祖先（LCA）来求解最短路径。

关键公式：

• 最小跳数 = depth(frm) + depth(to) - 2 * depth(LCA)

算法步骤

1. 解析层序遍历字符串，定位两个节点的索引位置
2. 如果节点不存在，返回 -1
3. 分别计算两个节点的深度
4. 将较深的节点上移，直到两个节点深度相同
5. 同时上移两个节点，直到找到最近公共祖先（LCA）
6. 根据深度差计算最小跳数

复杂度分析

• 时间复杂度：O(h)，其中 h 为树的高度，最大为 log₂N
• 空间复杂度：O(1)，只使用了常