2025A卷-传递悄悄话
题目描述
给定一个二叉树，每个节点上站着一个人，节点数字表示父节点到该节点传递悄悄话需要花费的时间。
开始时，根据节点所在位置的人有一个悄悄话想要传给其他人，求二叉树所有节点上的人都接收到悄悄话花费的时间。
输入描述
9 20 -1 -1 15 7 -1 -1 -1 -1 3 2
注：-1表示空节点
输出描述
返回所有节点都接受到悄悄话花费的时间。
用例
【用例一】
输入
0 -1 10 -1 -1
输出
10
说明：
根：0
根左：-1（空），根右：10
路径：0→10，总时间为 10。
【用例二】
输入
0 3 4 -1 -1 -1 -1
输出
4
说明：
根：0
根左：3，根右：4，均无子节点
两条路径：0→3 与 0→4，最大时间为 4。
Python代码实现
思路：
- 将二叉树的节点数字存放在数组中，父节点i，则左孩子节点为 2i+1，右孩子节点为 2i+2
- 如果这个节点的 左孩子节点 (i * 2 + 1)>=len(nums) 或 nums[2i+1]==-1 ，并且右孩子节点 (i * 2 + 2)>=len(nums) 或 nums[2i+2]==-1 ，这个节点就是叶子节点
- 或者用 dfs深度优先搜索
from typing import Listdef main(nums: List):n = len(nums)result = []# 先找到叶子节点, 父节点为i， 左孩子：2i+1, 右孩子：2i+2for i in range(n):path = []# 如果这个节点的 左孩子节点 (i * 2 + 1)>=len(nums) or nums[2*i+1]==-1 ，并且右孩子节点 (i * 2 + 2)>=len(nums) or nums[2*i+2]==-1 ，这个节点就是叶子节点if (2 * i + 1 >= n or nums[2 * i + 1] == -1) and (2 * i + 2 >= n or nums[2 * i + 2] == -1):if nums[i] == -1:continuepath.append(nums[i])index = i # 记录叶子节点的索引while index > 0:# 找到父节点，并添加index = (index - 1) // 2# print(index)path.insert(0, nums[index])if path:result.append(path)print(result)max_value = -1for num in result:max_value = max(max_value, sum(num))print(max_value)# 从根节点开始，递归获取左子树和右子树的最大花费时间
def dfs(nums: List, i):n = len(nums)if i >= n or nums[i] == -1:return 0# 递归搜索左右节点，去其中最大值left_value = dfs(nums, 2 * i + 1)right_value = dfs(nums, 2 * i + 2)max_value = max(left_value,right_value)return max_value + nums[i]def main_new(nums: List):# 输出根节点开始，输出最大值print(dfs(nums, 0))if __name__ == '__main__':nums = [9,20,-1,-1,15,7,-1,-1,-1,-1,3,2]# nums = [0, -1, 10, -1, -1]main(nums)main_new(nums)