当前位置：首页 > news >正文

5.30华为OD机试真题新系统 - 企业内部部门的最大层级 (Java/Py/C/C++/Js/Go)

news 2026/6/2 22:32:54

企业内部部门的最大层级

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

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

题目描述

企业的组织架构以树形结构表示，每个节点包含：

left: 左子部门（第一个子部门）

right: 右子部门（第二个子部门）

为了优化管理结构，实现扁平化管理，需要计算企业的最大管理层级深度。请计算企业的部门层级的最大深度。

注意

1、一个部门最多能有 2 个直属的子部门（二叉树）；

2、输入由数字和特殊符号#组成的序列，总结点数不超过 1024 个。数字表示该位置有子部门，#表示该位置无子部门（即无此节点）。

输入描述

输入由数字和特殊符号#组成的序列

输出描述

最大层级深度

示例1

输入

1,#,2,#,3,#,4,#,5

输出

说明

单链结构，深度为5

示例2

输入

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

输出

说明

完全二叉树，深度为4

示例3

输入

1,2,#

输出

说明

简单二叉树，深度为2

解题思路

本题是一个层序遍历 (BFS)问题，将数组视为二叉树的层序遍历序列。

关键概念：

输入是二叉树的层序遍历序列
“#” 表示该位置没有节点
需要计算从根到最深叶节点的层数

算法步骤

初始化：将根节点深度(1)加入队列
层序遍历：
- 弹出队首节点
- 检查左子节点：若存在，加入队列，更新最大深度
- 检查右子节点：若存在，加入队列，更新最大深度
返回结果：队列为空时返回最大深度

复杂度分析

时间复杂度: O(n)，遍历所有节点
空间复杂度: O(n)，队列存储

Java

importjava.util.*;publicclassMain{/** * 计算二叉树的最大深度 * * @param nodes 二叉树层序遍历数组 * @return 最大深度 */publicstaticintmaxDepth(String[]nodes){// 空树或根节点为空if(nodes==null||nodes.length==0||"#".equals(nodes[0])){return0;}// 队列中存储当前节点的深度Queue<Integer>queue=newLinkedList<>();queue.offer(1);intindex=1;intmaxDepth=1;// 按层序数组模拟 BFSwhile(!queue.isEmpty()){intdepth=queue.poll();// 处理左子节点if(index<nodes.length){if(!"#".equals(nodes[index])){queue.offer(depth+1);maxDepth=Math.max(maxDepth,depth+1);}index++;}// 处理右子节点if(index<nodes.length){if(!"#".equals(nodes[index])){queue.offer(depth+1);maxDepth=Math.max(maxDepth,depth+1);}index++;}}returnmaxDepth;}/** * 解析输入字符串 * 格式: 1,#,2,#,3,#,4,#,5 */publicstaticString[]parseInput(Stringline){line=line.trim();if(line.isEmpty()){returnnewString[0];}returnline.split(",");}publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);Stringline=scanner.nextLine().trim();String[]nodes=parseInput(line);intresult=maxDepth(nodes);System.out.println(result);scanner.close();}}

Python

fromcollectionsimportdequefromtypingimportListdefmax_depth(nodes:List[str])->int:""" 计算二叉树的最大深度 算法思路：层序遍历 (BFS) - 使用队列存储当前节点的深度 - 按层序遍历数组模拟二叉树 - 记录最大深度 时间复杂度: O(n) 空间复杂度: O(n) """# 空树或根节点为空ifnotnodesornodes[0]=="#":return0# 队列中存储当前节点的深度queue=deque([1])index=1max_depth_val=1# 按层序数组模拟 BFSwhilequeue:depth=queue.popleft()# 处理左子节点ifindex<len(nodes):ifnodes[index]!="#":queue.append(depth+1)max_depth_val=max(max_depth_val,depth+1)index+=1# 处理右子节点ifindex<len(nodes):ifnodes[index]!="#":queue.append(depth+1)max_depth_val=max(max_depth_val,depth+1)index+=1returnmax_depth_valdefparse_input(line:str)->List[str]:"""解析输入: 1,#,2,#,3,#,4,#,5"""line=line.strip()ifnotline:return[]return[x.strip()forxinline.split(',')]defmain():"""主函数"""line=input().strip()nodes=parse_input(line)result=max_depth(nodes)print(result)if__name__=="__main__":main()

JavaScript

/** * 计算二叉树的最大深度 * * @param {string[]} nodes - 二叉树层序遍历数组 * @returns {number} 最大深度 */functionmaxDepth(nodes){// 空树或根节点为空if(!nodes||nodes.length===0||nodes[0]==="#"){return0;}// 队列中存储当前节点的深度constqueue=[];queue.push(1);letindex=1;letmaxDepthVal=1;// 按层序数组模拟 BFSwhile(queue.length>0){constdepth=queue.shift();// 处理左子节点if(index<nodes.length){if(nodes[index]!=="#"){queue.push(depth+1);maxDepthVal=Math.max(maxDepthVal,depth+1);}index++;}// 处理右子节点if(index<nodes.length){if(nodes[index]!=="#"){queue.push(depth+1);maxDepthVal=Math.max(maxDepthVal,depth+1);}index++;}}returnmaxDepthVal;}/** * 解析输入字符串 * 格式: 1,#,2,#,3,#,4,#,5 */functionparseInput(line){line=line.trim();if(!line){return[];}returnline.split(',').map(x=>x.trim());}// 主函数 - 程序入口constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});rl.on('line',(line)=>{constnodes=parseInput(line);constresult=maxDepth(nodes);console.log(result);rl.close();});

C++

#include<iostream>#include<vector>#include<string>#include<queue>#include<sstream>#include<algorithm>usingnamespacestd;stringtrim(conststring&s){intleft=0;intright=(int)s.size()-1;while(left<=right&&s[left]==' '){left++;}while(right>=left&&s[right]==' '){right--;}returns.substr(left,right-left+1);}vector<string>split(conststring&data){vector<string>nodes;string item;stringstreamss(data);while(getline(ss,item,',')){nodes.push_back(trim(item));}returnnodes;}intmaxDepth(constvector<string>&nodes){if(nodes.empty()||nodes[0]=="#"){return0;}queue<int>q;q.push(1);intindex=1;intans=1;while(!q.empty()){intdepth=q.front();q.pop();if(index<(int)nodes.size()){if(nodes[index]!="#"){q.push(depth+1);ans=max(ans,depth+1);}index++;}if(index<(int)nodes.size()){if(nodes[index]!="#"){q.push(depth+1);ans=max(ans,depth+1);}index++;}}returnans;}intmain(){string data;getline(cin,data);if(data.empty()){cout<<0<<endl;return0;}vector<string>nodes=split(data);cout<<maxDepth(nodes)<<endl;return0;}

Go

packagemainimport("bufio""fmt""os""strings")/** * 计算二叉树的最大深度 */funcmaxDepth(nodes[]string)int{// 空树或根节点为空iflen(nodes)==0||nodes[0]=="#"{return0}// 使用队列存储索引和深度typeNodeDepthstruct{idxintdepthint}queue:=make([]NodeDepth,0)queue=append(queue,NodeDepth{0,1})maxDepthVal:=1forlen(queue)>0{node:=queue[0]queue=queue[1:]ifnode.depth>maxDepthVal{maxDepthVal=node.depth}// 左子节点索引leftIdx:=2*node.idx+1ifleftIdx<len(nodes)&&nodes[leftIdx]!="#"{queue=append(queue,NodeDepth{leftIdx,node.depth+1})}// 右子节点索引rightIdx:=2*node.idx+2ifrightIdx<len(nodes)&&nodes[rightIdx]!="#"{queue=append(queue,NodeDepth{rightIdx,node.depth+1})}}returnmaxDepthVal}/** * 解析输入字符串 */funcparseInput(linestring)[]string{line=strings.TrimSpace(line)ifline==""{return[]string{}}parts:=strings.Split(line,",")result:=make([]string,len(parts))fori,p:=rangeparts{result[i]=strings.TrimSpace(p)}returnresult}funcmain(){scanner:=bufio.NewScanner(os.Stdin)scanner.Scan()line:=scanner.Text()nodes:=parseInput(line)result:=maxDepth(nodes)fmt.Println(result)}

C语言

#include<stdio.h>#include<string.h>#include<stdlib.h>#include<ctype.h>#defineMAX_N1024#defineMAX_LEN10000voidtrim(char*s){intleft=0;intright=strlen(s)-1;while(left<=right&&isspace((unsignedchar)s[left])){left++;}while(right>=left&&isspace((unsignedchar)s[right])){right--;}intindex=0;for(inti=left;i<=right;i++){s[index++]=s[i];}s[index]='\0';}intmaxDepth(charnodes[][32],intn){if(n==0||strcmp(nodes[0],"#")==0){return0;}intqueue[MAX_N];intfront=0;intrear=0;queue[rear++]=1;intindex=1;intans=1;while(front<rear){intdepth=queue[front++];if(index<n){if(strcmp(nodes[index],"#")!=0){queue[rear++]=depth+1;if(depth+1>ans){ans=depth+1;}}index++;}if(index<n){if(strcmp(nodes[index],"#")!=0){queue[rear++]=depth+1;if(depth+1>ans){ans=depth+1;}}index++;}}returnans;}intmain(){chardata[MAX_LEN];if(fgets(data,sizeof(data),stdin)==NULL){printf("0\n");return0;}data[strcspn(data,"\n")]='\0';if(strlen(data)==0){printf("0\n");return0;}charnodes[MAX_N][32];intn=0;char*token=strtok(data,",");while(token!=NULL&&n<MAX_N){trim(token);strcpy(nodes[n++],token);token=strtok(NULL,",");}printf("%d\n",maxDepth(nodes,n));return0;}