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

硅谷探秘者 4753 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--;
	}
}



猜你喜欢
数据结构与算法 6348 题目:判断下方两棵右方是否为左方例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
数据结构与算法 7268 )java代码实现importjava.util.LinkedList;/***点类*@author硅谷探秘者(jia)*/classNode{ publicintdata; publicNodele
数据结构与算法 3929 堆排序(英语:Heapsort)是指利用堆这种所设计一种排序。堆是一个近似,并同时满足堆积性质:即子或索引总是小于(或者大于)它父节点。以最小堆为例下沉操
weblog 3062 什么是前驱节点和后继节点?某节点前驱节点val小于该节点val并且是最大那个节点。某节点后继节点val大于该节点val并且是最小那个节点。下面给出一个节点类
数据结构与算法 554 prim(普里姆)求出。对于任何一个,理解和实现只是一个方面,更重要是要明白它应用范围或应用场景,最小生成应用非常广泛,例如:假设要在n个城市之间建立通信联络网,则连接n个
数据结构与算法 4153 整理遍历-(递归)和(非递归)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//
数据结构与算法 598 原文链接:https://www.zhihu.com/question/23148377?sort=created基础 时间复杂度 空间复杂度基础 线性表 列表(必学) 链表(必学
数据结构与算法 387 思想:把所有需要排序分成两个集合,一个是待排序集合,一个是已排序集合,每次从未排序集合顺序或随机拿取一个,把它加入到已排序集合使其有序,直到未排序集合中被取走
归档
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
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议
目录
祝愿神州十三飞行乘组平安归来