目录题目思路Code题目题目内容给定一棵完全二叉树的层序遍历序列用逗号分隔的节点值字符串表示以及两个目标节点值 frm 和 to求这两个节点之间的最小跳数也就是最短路径经过的边数。完全二叉树按数组下标表示根节点索引为 0索引为 i 的节点父节点索引为 (i-1)//2左子节点索引为 2*i1右子节点索引为 2*i2。如果目标节点不存在返回 -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,323输出2说明从节点 2 到节点 3需要经过 2 到 1 再到 3共 2 跳。样例 2输入1,2,3,4,5,6,745输出2说明节点 4 和节点 5 是兄弟节点路径为 4 到 2 再到 5共 2 跳。思路二叉树先把层序遍历字符串按逗号拆开建立节点值到数组下标的映射。完全二叉树可以直接通过下标计算父节点下标 i 的父节点为 (i-1)//2。分别计算 frm 和 to 所在下标的深度让更深的节点先不断上跳直到两个节点处在同一层。两个节点同层后同步向父节点上跳第一次相遇的位置就是最近公共祖先。最小跳数等于 frm 到最近公共祖先的上跳次数加上 to 到最近公共祖先的上跳次数。如果 frm 或 to 不在映射中直接输出 -1如果两个节点相同且存在输出 0。Codeimport 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(,); MapString, 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)); } }Gopackage 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机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗?有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。