完全二叉树的权值(双指针)
二叉树 指针 完全 权值
2023-09-14 09:01:26 时间
Question
给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅AN,如下图所示:
QQ截图20191205124611.png
现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点权值之和最大?
如果有多个深度的权值和同为最大,请你输出其中最小的深度。
注:根的深度是 1。
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋅⋅⋅AN。
输出格式
输出一个整数代表答案。
数据范围
1≤N≤105,
−105≤Ai≤105
输入样例:
7
1 6 5 4 3 2 1
输出样例:
2
Ideas
i代表当前层的最小下标
j代表当前层的最大下标+1
Code
import math
res = 0
w_max = -float('inf')
h = 0 # 代表每一层数
n = int(input())
lis = list(int(i) for i in input().strip().split())
i,j = 0,1 # 做右指针
while h <= math.floor(math.log(n,2)): # 最多遍历math.log(n,2)(树的高度)次
w_sum = 0
h += 1 # 层数加1
# 求每一层的权重
for k in range(i,j):
w_sum += lis[k]
if w_sum > w_max:
res = h
w_max = w_sum
# 更改左右指针
i = j
j = 2 * i +1
# 越界情况
if j > n:
j = n - 1
print(res)
相关文章
- Java实现 LeetCode 559 N叉树的最大深度(遍历树,其实和便利二叉树一样,代码简短(●ˇ∀ˇ●))
- Java实现 LeetCode 102 二叉树的层次遍历
- Java实现 LeetCode 106 从中序与后序遍历序列构造二叉树
- java实现第六届蓝桥杯显示二叉树
- 一本正经的聊数据结构(6):最优二叉树 —— 哈夫曼树
- (剑指Offer)面试题61:按之字形顺序打印二叉树
- (剑指Offer)面试题25:二叉树中和为某一值的路径
- Python每日一练(20230329) 二叉树遍历
- Leetcode863. 二叉树中所有距离为 K 的结点(medium, BFS, DFS)
- 平衡二叉树(AVL)插入结点后的再平衡思路