数据结构-算法-完全二叉树的权值

硅谷探秘者 5243 0 0

试题描述:

image.png

image.png


思路:

        用数组表示完全二叉树,用先序遍历的方式遍历每一层的节点,用一个数组储存每一层的和,因为数据规模小于100000

所以用一个容量为17的数组即可。计算完每一层的和,再比较层数最小之和最大的那一层。

代码:

package club.test;

public class TestMain12 {
	/**
	 * 输入n
	 */
	static int a[]=new int[100000];
	/**
	 * 十万个数据二叉树最深也就17层吧
	 */
	static int m[]=new int[20];
	/**
	 * def遍历时二叉树的深度
	 */
	static int def=0;
	public static void main(String[] args) {
		for(int i=0;i<99999;i++) {
			a[i]=i;
		}
		dfs(1);
		int max=0;
		int c=0;
		for(int i=m.length-1;i>0;i--) {
			if(m[i]>max) {
				max=m[i];
				c=i;
			}
		}
		System.out.println(c);
	}
	/**
	 * 先序遍历二叉树
	 * @param index
	 */
	public static void dfs(int index){
		def++;
		if(index>=a.length) {
			return;
		}
		m[def]+=a[index];
		/**
		 * 向左节点遍历
		 */
		dfs(index<<1);
		def--;
		/**
		 * 向右节点遍历
		 */
		dfs((index<<1)+1);
		def--;
	}
}



猜你喜欢
数据结构与算法 6856 题目:判断下方两棵右方是否为左方例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
数据结构与算法 7731 )java代码实现importjava.util.LinkedList;/***点类*@author硅谷探秘者(jia)*/classNode{ publicintdata; publicNodele
数据结构与算法 4353 堆排序(英语:Heapsort)是指利用堆这种所设计一种排序。堆是一个近似,并同时满足堆积性质:即子或索引总是小于(或者大于)它父节点。以最小堆为例下沉操
weblog 3884 什么是前驱节点和后继节点?某节点前驱节点val小于该节点val并且是最大那个节点。某节点后继节点val大于该节点val并且是最小那个节点。下面给出一个节点类
数据结构与算法 1057 prim(普里姆)求出。对于任何一个,理解和实现只是一个方面,更重要是要明白它应用范围或应用场景,最小生成应用非常广泛,例如:假设要在n个城市之间建立通信联络网,则连接n个
数据结构与算法 4603 整理遍历-(递归)和(非递归)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//
数据结构与算法 1243 原文链接:https://www.zhihu.com/question/23148377?sort=created基础 时间复杂度 空间复杂度基础 线性表 列表(必学) 链表(必学
数据结构与算法 798 思想:把所有需要排序分成两个集合,一个是待排序集合,一个是已排序集合,每次从未排序集合顺序或随机拿取一个,把它加入到已排序集合使其有序,直到未排序集合中被取走
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16 2021年12月  14 2022年01月  7 2022年05月  1 2022年08月  3 2022年09月  2 2022年10月  2 2022年12月  5 2023年01月  3
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。