目录
题目
思路
Code
题目
题目内容
给定一棵完全二叉树的层序遍历序列，用逗号分隔的节点值字符串表示，以及两个目标节点值 frm 和 to，求这两个节点之间的最小跳数，也就是最短路径经过的边数。
完全二叉树按数组下标表示，根节点索引为 0，索引为 i 的节点父节点索引为 (i-1)//2，左子节点索引为 2*i+1，右子节点索引为 2*i+2。
如果目标节点不存在，返回 -1。如果 frm 和 to 相同且节点存在，返回 0。树的节点不重名，节点数量范围公开页面仅能确认到 1 到 10^6。
输入描述
第一行输入字符串形式的层序遍历序列，节点值用逗号分隔，例如 1,2,3,4,5,6,7。
第二行输入起始节点值 frm。
第三行输入目标节点值 to。
输出描述
输出一个整数，表示从 frm 到 to 的最小跳数。如果任一节点不存在，输出 -1。如果 frm 等于 to 且节点存在，输出 0。
样例 1
输入
1,2,3
2
3
输出
2
说明
从节点 2 到节点 3，需要经过 2 到 1 再到 3，共 2 跳。
样例 2
输入
1,2,3,4,5,6,7
4
5
输出
2
说明
节点 4 和节点 5 是兄弟节点，路径为 4 到 2 再到 5，共 2 跳。
思路
二叉树
先把层序遍历字符串按逗号拆开，建立节点值到数组下标的映射。
完全二叉树可以直接通过下标计算父节点，下标 i 的父节点为 (i-1)//2。
分别计算 frm 和 to 所在下标的深度，让更深的节点先不断上跳，直到两个节点处在同一层。
两个节点同层后同步向父节点上跳，第一次相遇的位置就是最近公共祖先。
最小跳数等于 frm 到最近公共祖先的上跳次数，加上 to 到最近公共祖先的上跳次数。
如果 frm 或 to 不在映射中，直接输出 -1；如果两个节点相同且存在，输出 0。
Code
import java.util.*; public class Main { private static int depth(int pos) { // 完全二叉树用数组下标表示，反复跳到父节点即可得到层数。 int d = 0; while (pos > 0) { pos = (pos - 1) / 2; d++; } return d; } private static int minJumps(String treeLine, String from, String to) { String[] nodes = treeLine.split(","); Map<String, Integer> index = new HashMap<>(); // 先记录节点值第一次出现的位置，避免后续查找时重复扫描数组。 for (int i = 0; i < nodes.length; i++) { index.putIfAbsent(nodes[i].trim(), i); } if (!index.containsKey(from) || !index.containsKey(to)) { return -1; } if (from.equals(to)) { return 0; } int a = index.get(from), b = index.get(to); int da = depth(a), db = depth(b); int originalDa = da, originalDb = db; while (da > db) { // 让更深的节点先上移，保证两个候选节点处在同一层。 a = (a - 1) / 2; da--; } while (db > da) { b = (b - 1) / 2; db--; } while (a != b) { // 同步上移直到下标相同，此时就是最近公共祖先。 a = (a - 1) / 2; b = (b - 1) / 2; } return originalDa + originalDb - 2 * depth(a); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); if (!sc.hasNextLine()) return; String treeLine = sc.nextLine().trim(); if (!sc.hasNextLine()) return; String from = sc.nextLine().trim(); if (!sc.hasNextLine()) return; String to = sc.nextLine().trim(); System.out.println(minJumps(treeLine, from, to)); } }Go
package main import ( "bufio" "fmt" "os" "strings" ) func depth(pos int) int { // 完全二叉树用数组下标表示，反复跳到父节点即可得到层数。 d := 0 for pos > 0 { pos = (pos - 1) / 2 d++ } return d } func main() { in := bufio.NewScanner(os.Stdin) lines := []string{} for in.Scan() { text := strings.TrimSpace(in.Text()) if text != "" { lines = append(lines, text) } } if len(lines) < 3 { return } nodesRaw := strings.Split(lines[0], ",") index := map[string]int{} for i, node := range nodesRaw { // 题面按逗号给出层序数组，这里去掉空白后建立节点到下标的映射。 value := strings.TrimSpace(node) if _, ok := index[value]; !ok { index[value] = i } } a, okA := index[lines[1]] b, okB := index[lines[2]] if !okA || !okB { fmt.Println(-1) return } if lines[1] == lines[2] { fmt.Println(0) return } da, db := depth(a), depth(b) originalDa, originalDb := da, db for da > db { // 让更深的节点先上移，保证两个候选节点处在同一层。 a = (a - 1) / 2 da-- } for db > da { b = (b - 1) / 2 db-- } for a != b { // 同步上移直到下标相同，此时就是最近公共祖先。 a = (a - 1) / 2 b = (b - 1) / 2 } fmt.Println(originalDa + originalDb - 2*depth(a)) }C
#include <stdio.h> #include <string.h> #include <ctype.h> #define MAXN 1000005 #define MAXL 64 char nodes[MAXN][MAXL]; int depth_of(int pos) { // 完全二叉树用数组下标表示，反复跳到父节点即可得到层数。 int depth = 0; while (pos > 0) { pos = (pos - 1) / 2; depth++; } return depth; } int find_node(int n, const char *target) { for (int i = 0; i < n; i++) { if (strcmp(nodes[i], target) == 0) return i; } return -1; } int main() { static char line[MAXN * 2]; char from[MAXL], to[MAXL]; if (!fgets(line, sizeof(line), stdin)) return 0; if (!fgets(from, sizeof(from), stdin)) return 0; if (!fgets(to, sizeof(to), stdin)) return 0; from[strcspn(from, "\r\n")] = '\0'; to[strcspn(to, "\r\n")] = '\0'; int n = 0, len = 0; for (int i = 0; line[i]; i++) { // 题面按逗号给出层序数组，这里去掉空白后拆成节点值。 char ch = line[i]; if (ch == ',' || ch == '\n' || ch == '\r') { nodes[n][len] = '\0'; n++; len = 0; if (ch == '\n' || ch == '\r') break; } else if (!isspace((unsigned char)ch) && len + 1 < MAXL) { nodes[n][len++] = ch; } } if (len > 0) { nodes[n][len] = '\0'; n++; } int a = find_node(n, from); int b = find_node(n, to); if (a == -1 || b == -1) { printf("-1\n"); return 0; } if (strcmp(from, to) == 0) { printf("0\n"); return 0; } int da = depth_of(a), db = depth_of(b); int original_da = da, original_db = db; while (da > db) { // 让更深的节点先上移，保证两个候选节点处在同一层。 a = (a - 1) / 2; da--; } while (db > da) { b = (b - 1) / 2; db--; } while (a != b) { // 同步上移直到下标相同，此时就是最近公共祖先。 a = (a - 1) / 2; b = (b - 1) / 2; } printf("%d\n", original_da + original_db - 2 * depth_of(a)); return 0; }【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集
【华为od机试真题Python】：Python真题题库
【华为od机试真题JavaScript】：JavaScript真题题库
【华为od机试真题Java&Go】：Java&Go真题题库
【华为od机试真题C++】：C++真题题库
【华为od机试真题C语言】：C语言真题题库
【华为od面试手撕代码题库】：面试手撕代码题库
【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】
华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
