数据结构-算法-完全二叉树的权值
试题描述:
思路:
用数组表示完全二叉树,用先序遍历的方式遍历每一层的节点,用一个数组储存每一层的和,因为数据规模小于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
blog
数据结构+算法-堆排序
数据结构与算法
4353
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。以最小堆为例下沉操
weblog
3884
什么是二叉树的前驱节点和后继节点?某节点的前驱节点的val值小于该节点的val值并且值是最大的那个节点。某节点的后继节点的val值大于该节点的val值并且值是最小的那个节点。下面给出一个二叉树节点类
数据结构与算法
1057
prim(普里姆)算法求出。对于任何一个数据结构或算法,理解和实现只是一个方面,更重要的是要明白它的应用范围或应用场景,最小生成树算法的应用非常广泛,例如:假设要在n个城市之间建立通信联络网,则连接n个
blog
二叉树的遍历-(递归法)和(非递归法)
数据结构与算法
4603
整理二叉树的遍历-(递归法)和(非递归法)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//数据域
blog
程序员必须掌握的数据结构和算法
数据结构与算法
1243
原文链接:https://www.zhihu.com/question/23148377?sort=created算法基础 时间复杂度 空间复杂度基础数据结构 线性表 列表(必学) 链表(必学
blog
插入排序 - 数据结构与算法
数据结构与算法
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
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。