二叉树两节点间的最小跳数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特殊情况见用例。输入描述第一行字符串形式的层序遍历序列节点值用逗号分隔例如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 下方最小跳数为 24 - 2 - 5。解题思路核心思想利用完全二叉树的数组表示特性通过计算两个节点的深度和最近公共祖先LCA来求解最短路径。关键公式最小跳数 depth(frm) depth(to) - 2 * depth(LCA)算法步骤解析层序遍历字符串定位两个节点的索引位置如果节点不存在返回 -1分别计算两个节点的深度将较深的节点上移直到两个节点深度相同同时上移两个节点直到找到最近公共祖先LCA根据深度差计算最小跳数复杂度分析时间复杂度O(h)其中 h 为树的高度最大为 log₂N空间复杂度O(1)只使用了常量额外空间Javaimportjava.util.*;publicclassMain{publicstaticintminJumps(StringtreeLevelOrder,Stringfrm,Stringto){String[]nodestreeLevelOrder.split(,);for(inti0;inodes.length;i){nodes[i]nodes[i].trim();}intposFrm-1,posTo-1;for(inti0;inodes.length;i){if(nodes[i].equals(frm))posFrmi;if(nodes[i].equals(to))posToi;}if(posFrm-1||posTo-1)return-1;intd1depth(posFrm);intd2depth(posTo);intorigD1d1,origD2d2;while(d1d2){posFrm(posFrm-1)/2;d1--;}while(d2d1){posTo(posTo-1)/2;d2--;}while(posFrm!posTo){posFrm(posFrm-1)/2;posTo(posTo-1)/2;}returnorigD1origD2-2*depth(posFrm);}privatestaticintdepth(intpos){intd0;while(pos0){pos(pos-1)/2;d;}returnd;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);StringtreeLevelOrdersc.nextLine().trim();Stringfrmsc.nextLine().trim();Stringtosc.nextLine().trim();System.out.println(minJumps(treeLevelOrder,frm,to));}}Pythondefmin_jumps(tree_level_order,frm,to):nodes[n.strip()fornintree_level_order.split(,)]pos_frmpos_to-1fori,nodeinenumerate(nodes):ifnodefrm:pos_frmiifnodeto:pos_toiifpos_frm-1orpos_to-1:return-1defdepth(pos):d0whilepos0:pos(pos-1)//2d1returnd d1,d2depth(pos_frm),depth(pos_to)orig_d1,orig_d2d1,d2whiled1d2:pos_frm(pos_frm-1)//2d1-1whiled2d1:pos_to(pos_to-1)//2d2-1whilepos_frm!pos_to:pos_frm(pos_frm-1)//2pos_to(pos_to-1)//2returnorig_d1orig_d2-2*depth(pos_frm)if__name____main__:tree_level_orderinput().strip()frminput().strip()toinput().strip()print(min_jumps(tree_level_order,frm,to))JavaScriptfunctionminJumps(treeLevelOrder,frm,to){constnodestreeLevelOrder.split(,).map(nn.trim());letposFrm-1,posTo-1;for(leti0;inodes.length;i){if(nodes[i]frm)posFrmi;if(nodes[i]to)posToi;}if(posFrm-1||posTo-1)return-1;constdepth(pos){letd0;while(pos0){posMath.floor((pos-1)/2);d;}returnd;};letd1depth(posFrm);letd2depth(posTo);constorigD1d1,origD2d2;while(d1d2){posFrmMath.floor((posFrm-1)/2);d1--;}while(d2d1){posToMath.floor((posTo-1)/2);d2--;}while(posFrm!posTo){posFrmMath.floor((posFrm-1)/2);posToMath.floor((posTo-1)/2);}returnorigD1origD2-2*depth(posFrm);}constreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin});constlines[];rl.on(line,(line)lines.push(line.trim()));rl.on(close,(){console.log(minJumps(lines[0],lines[1],lines[2]));});C#includebits/stdc.husingnamespacestd;intdepth(intpos){intd0;while(pos0){pos(pos-1)/2;d;}returnd;}intminJumps(string treeLevelOrder,string frm,string to){vectorstringnodes;stringstreamss(treeLevelOrder);string node;while(getline(ss,node,,)){nodes.push_back(node);}intposFrm-1,posTo-1;for(inti0;inodes.size();i){if(nodes[i]frm)posFrmi;if(nodes[i]to)posToi;}if(posFrm-1||posTo-1)return-1;intd1depth(posFrm);intd2depth(posTo);intorigD1d1,origD2d2;while(d1d2){posFrm(posFrm-1)/2;d1--;}while(d2d1){posTo(posTo-1)/2;d2--;}while(posFrm!posTo){posFrm(posFrm-1)/2;posTo(posTo-1)/2;}returnorigD1origD2-2*depth(posFrm);}intmain(){string treeLevelOrder,frm,to;getline(cin,treeLevelOrder);getline(cin,frm);getline(cin,to);coutminJumps(treeLevelOrder,frm,to)endl;return0;}Gopackagemainimport(bufiofmtosstrings)funcdepth(posint)int{d:0forpos0{pos(pos-1)/2d}returnd}funcminJumps(treeLevelOrder,frm,tostring)int{nodes:strings.Split(treeLevelOrder,,)fori:rangenodes{nodes[i]strings.TrimSpace(nodes[i])}posFrm,posTo:-1,-1fori,node:rangenodes{ifnodefrm{posFrmi}ifnodeto{posToi}}ifposFrm-1||posTo-1{return-1}d1:depth(posFrm)d2:depth(posTo)origD1,origD2:d1,d2ford1d2{posFrm(posFrm-1)/2d1--}ford2d1{posTo(posTo-1)/2d2--}forposFrm!posTo{posFrm(posFrm-1)/2posTo(posTo-1)/2}returnorigD1origD2-2*depth(posFrm)}funcmain(){in:bufio.NewReader(os.Stdin)vartreeLevelOrder,frm,tostringfmt.Fscan(in,treeLevelOrder)fmt.Fscan(in,frm)fmt.Fscan(in,to)fmt.Println(minJumps(treeLevelOrder,frm,to))}C语言#includestdio.h#includestdlib.h#includestring.h#includectype.h#defineMAX_LINE10000005voidtrim(char*s){intleft0;intright(int)strlen(s)-1;while(leftrightisspace((unsignedchar)s[left])){left;}while(rightleftisspace((unsignedchar)s[right])){right--;}intlenright-left1;if(len0){memmove(s,sleft,len);}s[len0?len:0]\0;}intdepth(longlongpos){intd0;while(pos0){pos(pos-1)/2;d;}returnd;}intmin_jumps(char*tree_level_order,char*frm,char*to){longlongpos_frm-1;longlongpos_to-1;longlongindex0;char*starttree_level_order;char*ptree_level_order;while(1){if(*p,||*p\0){charsaved*p;*p\0;trim(start);if(strcmp(start,frm)0){pos_frmindex;}if(strcmp(start,to)0){pos_toindex;}index;if(saved\0){break;}*psaved;startp1;}p;}if(pos_frm-1||pos_to-1){return-1;}intd1depth(pos_frm);intd2depth(pos_to);intorig_d1d1;intorig_d2d2;while(d1d2){pos_frm(pos_frm-1)/2;d1--;}while(d2d1){pos_to(pos_to-1)/2;d2--;}while(pos_frm!pos_to){pos_frm(pos_frm-1)/2;pos_to(pos_to-1)/2;}returnorig_d1orig_d2-2*depth(pos_frm);}intmain(){char*tree_level_order(char*)malloc(MAX_LINE);charfrm[MAX_LINE];charto[MAX_LINE];fgets(tree_level_order,MAX_LINE,stdin);fgets(frm,MAX_LINE,stdin);fgets(to,MAX_LINE,stdin);trim(tree_level_order);trim(frm);trim(to);printf(%d\n,min_jumps(tree_level_order,frm,to));free(tree_level_order);return0;}完整用例用例11,2,3 2 3用例21,2,3,4,5,6,7 4 5用例31,2,3,4,5,6,7 1 4用例41,2,3,4,5,6,7 4 2用例51,2,3,4,5,6,7 4 7用例61,2,3 X 2用例71,2,3 2 2用例81,2,3,4,5,6,7,8,9,10,11,12,13,14,15 8 15用例91,2,3 2 3用例101 1 1文章目录二叉树两节点间的最小跳数题目描述输入描述输出描述示例1示例2解题思路核心思想算法步骤复杂度分析JavaPythonJavaScriptCGoC语言完整用例用例1用例2用例3用例4用例5用例6用例7用例8用例9用例10