精美网站制作公司安徽做手机网站

精美网站制作公司,安徽做手机网站,建筑资料哪个网最全,企业网上年检在网站怎么做题目描述有一个 n(n≤10^6) 个结点的二叉树。给出每个结点的两个子结点编号#xff08;均不超过 n#xff09;#xff0c;建立一棵二叉树#xff08;根节点的编号为 1#xff09;#xff0c;如果是叶子结点#xff0c;则输入 0 0。建好这棵二叉树之后#xff0c;请求出…题目描述有一个 n(n≤10^6) 个结点的二叉树。给出每个结点的两个子结点编号均不超过 n建立一棵二叉树根节点的编号为 1如果是叶子结点则输入0 0。建好这棵二叉树之后请求出它的深度。二叉树的深度是指从根节点到叶子结点时最多经过了几层。输入格式第一行一个整数 n表示结点数。之后 n 行第 i 行两个整数 l、r分别表示结点 i 的左右子结点编号。若 l0 则表示无左子结点r0 同理。输出格式一个整数表示最大结点深度。输入输出样例输入 #1复制7 2 7 3 6 4 5 0 0 0 0 0 0 0 0输出 #1复制4问题分析与核心思路本题要求计算给定二叉树的最大深度。我们采用广度优先搜索 (BFS)来解决因为它天然地按层级遍历。BFS 特性保证先访问层级低的节点后访问层级高的节点。深度计算在遍历过程中利用父节点的深度信息推算出子节点的深度父节点深度 1。最终答案所有节点中记录的最大层级值即为树的最大深度。 数据结构设计为了存储树结构和节点深度我们定义了结构体nodestruct node{ int l;//左儿子 int r;//右儿子 int level;//节点所在层级/深度 }a[1000001];a数组存储所有节点信息。queuenode q用于辅助 BFS 遍历。ma记录当前已知的最大深度。BFS 算法实现 (bfs函数)bfs函数实现了核心的层序遍历逻辑。1. 初始化将根节点编号 1入队并假设其深度已初始化为 1。2. 循环遍历使用while(!q.empty())进行循环。出队访问node tmpq.front(); q.pop();处理左儿子if(tmp.l!0){ // 检查左儿子是否存在 // 关键a[i].level 0 标记节点是否已访问 if(a[tmp.l].level0){ a[tmp.l].leveltmp.level1; // 新深度 父节点深度 1 q.push(a[tmp.l]); // 左儿子入队 mamax(ma,a[tmp.l].level); // 更新最大深度 } }处理右儿子处理逻辑与左儿子相同确保右儿子也入队并更新最大深度。3. 结果输出遍历完成后输出ma。完整代码流程在main函数中我们负责读取数据、初始化根节点深度并调用 BFS 函数。//洛谷P4913 【深基16.例3】二叉树深度 #include iostream #include queue using namespace std; struct node{ int l;//左儿子 int r;//右儿子 int level;//节点所在层次 }a[1000001]; int ma0; queuenode q; void bfs(int root){//根节点传进来 node tmp; tmpa[root]; q.push(tmp);//根节点入队 while(!q.empty()){ tmpq.front();//访问队首元素 q.pop();//队首出队 //得有左儿子 if(tmp.l!0) { //左儿子没有走过 if(a[tmp.l].level0){ a[tmp.l].leveltmp.level1; q.push(a[tmp.l]);//没有访问过就入队 mamax(ma,a[tmp.l].level); } } //得有右儿子 if(tmp.r!0){ //右儿子没有走过 if(a[tmp.r].level0){ a[tmp.r].leveltmp.level1; q.push(a[tmp.r]); mamax(ma,a[tmp.r].level); } } } coutma; } int main(){ int n; cinn; for(int i1;in;i) cina[i].la[i].r; a[1].level1; ma1; bfs(1); return 0; }