🍭 大家好這里是清隆學長 ，一枚熱愛算法的程序員

? 本系列打算持續跟新華為OD-C卷的三語言AC題解

💻 ACM銀牌🥈| 多次AK大廠筆試 ｜ 編程一對一輔導

👏 感謝大家的訂閱? 和 喜歡💗

前言

🧭 機試備考指南

• 華為OD的題庫大半年跟新一次，也就是說，一旦跟新，那么本年用的題目就是從該題庫種選題，大概有100～200道左右

• 最近考試換為C/D卷，C/D卷題庫是一樣的，D卷為雙機位監控，某些外包公司應聘的為D卷。

• 為此清隆幫大家搜集并整理了C卷的題庫，后續會由清隆的ACM銀牌團隊將題目整理后搬上OJ，支持在線評測。

💊 傳遞悄悄話的最長時間

題目描述

在一個大家庭的聚會上，家庭成員站在由二叉樹形式組織的位置上。每個位置上有一人，每個人之間的連接代表一條傳遞悄悄話的路徑，且這條路徑上有一個時間消耗。現在，根位置的K小姐想將一個悄悄話傳遞給所有人。每個連接的數字表示K小姐傳遞悄悄話給該節點的人所需額外時間。請計算使得所有家庭成員都聽到這個悄悄話所需的最長時間。

輸入格式

輸入包含一行，由空格隔開的整數序列。這個序列以層序遍歷的方式描述了一個二叉樹，其中 -1 表示空節點。序列的第一個數字是根節點，表示從K小姐開始的時間為0。

輸出格式

輸出一個整數，表示所有節點都接收到悄悄話的最長時間。

樣例輸入

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

樣例輸出

38

數據范圍

輸入的二叉樹節點個數不超過 $1000$，時間都是非負整數，不超過 $100$。

題解

這個題目的核心是對二叉樹進行遍歷，并計算從根節點到每一個節點的路徑時間。由于使用的是層序遍歷的輸入方式，我們可以使用隊列來幫助我們構造這個二叉樹，并同時計算從根節點到其他節點的時間。我們需要追蹤的是從根節點到每個節點的累計時間，最終輸出最大的那個時間，即為所有人都接收到悄悄話的最長時間。

參考代碼

• Cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;int main() {vector<int> input;int tmp;while (cin >> tmp) {input.push_back(tmp);}if (input.empty() || input[0] == -1) {cout << "0" << endl;return 0;}queue<pair<int, int>> q; // pair<index, time>q.push({0, input[0]});int maxTime = 0;while (!q.empty()) {auto [index, currTime] = q.front();q.pop();maxTime = max(maxTime, currTime);int leftChildIndex = 2 * index + 1;int rightChildIndex = 2 * index + 2;if (leftChildIndex < input.size() && input[leftChildIndex] != -1) {q.push({leftChildIndex, currTime + input[leftChildIndex]});}if (rightChildIndex < input.size() && input[rightChildIndex] != -1) {q.push({rightChildIndex, currTime + input[rightChildIndex]});}}cout << maxTime << endl;return 0;
}

• Python

from queue import Queueinput_str = input().split()
input = [int(x) if x != '-1' else -1 for x in input_str]if not input or input[0] == -1:print("0")exit()q = Queue()
q.put((0, input[0]))
max_time = 0while not q.empty():index, curr_time = q.get()max_time = max(max_time, curr_time)left_child_index = 2 * index + 1right_child_index = 2 * index + 2if left_child_index < len(input) and input[left_child_index] != -1:q.put((left_child_index, curr_time + input[left_child_index]))if right_child_index < len(input) and input[right_child_index] != -1:q.put((right_child_index, curr_time + input[right_child_index]))print(max_time)

• Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class MaxSumPath {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String[] inputStr = scanner.nextLine().split(" ");int[] input = new int[inputStr.length];for (int i = 0; i < inputStr.length; i++) {input[i] = Integer.parseInt(inputStr[i]);}if (input.length == 0 || input[0] == -1) {System.out.println("0");return;}Queue<Pair> queue = new LinkedList<>();queue.add(new Pair(0, input[0]));int maxTime = 0;while (!queue.isEmpty()) {Pair pair = queue.poll();int index = pair.index;int currTime = pair.time;maxTime = Math.max(maxTime, currTime);int leftChildIndex = 2 * index + 1;int rightChildIndex = 2 * index + 2;if (leftChildIndex < input.length && input[leftChildIndex] != -1) {queue.add(new Pair(leftChildIndex, currTime + input[leftChildIndex]));}if (rightChildIndex < input.length && input[rightChildIndex] != -1) {queue.add(new Pair(rightChildIndex, currTime + input[rightChildIndex]));}}System.out.println(maxTime);}static class Pair {int index;int time;Pair(int index, int time) {this.index = index;this.time = time;}}
}

🍓 AC代碼截圖 ?

• Python