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

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

华为od机试

题目描述

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

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

输入描述

给定二叉树

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

注： -1 表示空节点

传递悄悄话

输出描述

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

示例1

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

输出：
38

题解

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

使用 深度优先搜索 (DFS) 来解决此问题，递归遍历整棵树，计算从根节点传递到最远叶子节点的时间。

我们对每个节点，递归计算其左右子树的最大传递时间，选择较大的那一条路径，并加上当前节点的传递时间。

解题思路

递归思路：

对于每个节点，从左子树和右子树递归地计算最大传递时间。

当到达叶子节点时，递归结束，返回0。

对于每个非叶节点，返回其左、右子树中较大的传递时间，加上该节点的时间。

特殊情况：

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

输入表示：

使用层次遍历的方式输入二叉树，-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 + 2);

        // 返回当前节点的传递时间加上左右子树的最大时间
        return Math.max(leftTime, rightTime) + arr[pos];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = Arrays.stream(scanner.nextLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();

        // 输出从根节点传递悄悄话的最大时间
        System.out.println(dfs(arr, 0));
    }
}

Python

# 将输入的二叉树转化为数组形式
arr = list(map(int, input().split()))
n = len(arr)

def dfs(pos):
    """
    :param pos:  当前节点在数组中的索引
    :return:  消息从当前节点传递到叶子节点的最大花费时间
    """
    global arr, n
    if pos >= n or arr[pos] == -1:  # 超出范围或空节点
        return 0
    
    # 递归获取左子树和右子树的最大花费时间
    left_time = dfs(pos * 2 + 1)
    right_time = dfs(pos * 2 + 2)
    
    # 返回当前节点的传递时间 + 左右子树最大花费时间
    return max(left_time, right_time) + arr[pos]

# 输出根节点开始传递悄悄话的最大时间
print(dfs(0))

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> arr;
int n;

int dfs(int pos) {
    // 如果超出数组范围或当前节点为空，返回 0
    if (pos >= n || arr[pos] == -1) return 0;

    // 递归获取左右子树的最大时间
    int leftTime = dfs(pos * 2 + 1);
    int rightTime = dfs(pos * 2 + 2);

    // 返回当前节点的传递时间加上左右子树的最大时间
    return max(leftTime, rightTime) + arr[pos];
}

int main() {
    // 读入数据
    int num;
    while (cin >> num) arr.push_back(num);

    n = arr.size();

    // 输出根节点开始传递悄悄话的最大时间
    cout << dfs(0) << endl;

    return 0;
}