xr

用户名：dotcpp0639023

访问量：410

签　名：

等　　级
排　　名	2377
经　　验	2337
参赛次数	0
文章发表	5
年　　龄	23
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

子串分值和-贡献值法，详细样例解释
浏览：87

你可能喜欢

C语言程序设计教程（第三版）课后习题4.9 （Java代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

完全二叉树的权值最详细注释

　　作者: xr　　　　发表时间：2023-03-06 11:15:15 浏览：83　|　评论：0　

原题链接：蓝桥杯2019年第十届省赛真题-完全二叉树的权值

利用树的性质

主要两个点：
1. 最后一层节点可能不是满的，所以需要加上这个判断条件 (i == n-1)
2. 下一层的节点数是上一层的节点数*2，通过判断当前第几个节点是否==该层总结点数，来确定是否到达该层最后一个，若是则需要将当前第几个节点和该层权值和置零，方便下一层计数

```java
import java.util.Scanner;

public class 第十届_完全二叉树的权值 {
	static int n;
	static int[] tree;
	static int sum;		// 某深度的最大权值
	static int tempSum;	// 当前深度所有节点的权值
	static int dept;	// 存放结果即权值最大的最小深度
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		tree = new int[n];
		for(int i = 0; i<n; i++) {
			tree[i] = sc.nextInt();
		}
		
		/**
		 * curDept 当前深度
		 * curDeptCount 当前深度的第几个
		 * curDeptNum	当前深度总共有几个节点
		 */
		for(int i = 0, curDept = 1, curDeptCount = 1, curDeptNum = 1; i<n; i++,curDeptCount++) {
			if(i == 0) {	// 第一层即根节点，直接把权值赋值
				sum = tree[i];	
				dept = curDept;
			}
			else {	// 计算每一层
				if(curDeptCount == 1) {	// 当前层的第一个，则将深度+1
					curDept++;
					tempSum += tree[i];
//					curDeptCount++;
				} else {
					tempSum += tree[i];
//					curDeptCount++;
				}
				if(tempSum > sum && i == n-1) {	// 如果最后一层不是满的并且该层权值和大于sum，则赋值
					sum = tempSum;
//					curDeptCount = 0;
//					tempSum = 0;
					dept = curDept;
				}
			}
			if(curDeptCount == curDeptNum) {	// 如果走到该层最后一个
				if(tempSum > sum) {
					sum = tempSum;
					dept = curDept;
				}
				// 需要将下一层的总节点数算出来
				curDeptNum*=2;
				// 置零，方便下一层计数
				curDeptCount = 0;
				tempSum = 0;
			}
		}
		System.out.print(dept);
	}
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

xr

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题4.9 （Java代码）

汽水瓶（C语言代码）

printf基础练习2 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

C二级辅导-分段函数（C语言代码）

完全二叉树的权值最详细注释

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

母牛的故事（C语言代码）

校门外的树（C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

数组输出（C语言代码）

【绝对值排序】（C++代码）

上车人数（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

xr

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题4.9 （Java代码）

汽水瓶 （C语言代码）

printf基础练习2 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C++代码）

C二级辅导-分段函数 （C语言代码）

完全二叉树的权值最详细注释

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

母牛的故事 （C语言代码）

校门外的树 （C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

数组输出 （C语言代码）

【绝对值排序】 （C++代码）

上车人数 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

汽水瓶（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

C二级辅导-分段函数（C语言代码）

　　评论区

母牛的故事（C语言代码）

校门外的树（C语言代码）

数组输出（C语言代码）

【绝对值排序】（C++代码）

上车人数（C语言代码）

C二级辅导-阶乘数列（C语言代码）