传递悄悄话 - 华为OD统一考试(E卷)

2024华为OD机试（C卷+D卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

给定一个二叉树，每个节点上站一个人，节点数字表示父节点到该节点传递悄悄话需要花费的时间。

初始时，根节点所在位置的人有一个悄悄话想要传递给其他人，求二叉树所有节点上的人都接收到悄悄话花费的时间。

输入描述

给定二叉树

0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2

注： -1 表示空节点

输出描述

返回所有节点都接收到悄悄话花费的时间

38

示例1

输入：
0 9 20 -1 -1 15 15 7 -1 -1 -1 -1 3 2

输出：
38

题解

题目要求从二叉树的根节点开始，将悄悄话传递到所有节点，计算所花费的时间。每个节点的值表示将悄悄话从父节点传递到该节点所需的时间。

• 使用 深度优先搜索 (DFS) 来解决此问题，递归遍历整棵树，计算从根节点传递到最远叶子节点的时间。
• 我们对每个节点，递归计算其左右子树的最大传递时间，选择较大的那一条路径，并加上当前节点的传递时间。

解题思路

1. 递归思路：

   • 对于每个节点，从左子树和右子树递归地计算最大传递时间。
   • 当到达叶子节点时，递归结束，返回0。
   • 对于每个非叶节点，返回其左、右子树中较大的传递时间，加上该节点的时间。

2. 特殊情况：

   • 如果节点为 -1，表示该节点为空，不需要继续传递，直接返回0。

3. 输入表示：

   • 使用层次遍历的方式输入二叉树，-1 表示空节点。

时间复杂度：O(N)，其中 N 是二叉树的节点数。每个节点都会被访问一次。

空间复杂度：O(H)，其中 H 是树的高度。递归调用的深度取决于树的高度。

Java

import java.util.Arrays;
import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static int dfs(int[] arr, int pos) {
        if (pos >= arr.length || arr[pos] == -1) {
            return 0;
        }
        // 递归计算左子树和右子树的最大传递时间
        int leftTime = dfs(arr, pos * 2 + 1);
        int rightTime = dfs(arr, pos * 2