2025 A卷 200分 題型

本專欄內全部題目均提供Java、python、JavaScript、C、C++、GO六種語言的最佳實現方式；

并且每種語言均涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、3個測試用例以及綜合分析；

本文收錄于專欄：《2025華為OD真題目錄+全流程解析+備考攻略+經驗分享》

華為OD機試真題《傳遞悄悄話（二叉樹最長路徑問題）》：

---

文章快捷目錄

題目描述及說明

Java

python

JavaScript

C++

C

GO

---

題目名稱：傳遞悄悄話（二叉樹最長路徑問題）

---

1. 知識點：二叉樹、DFS/BFS、路徑和計算
2. 時間限制：1秒
3. 空間限制：256MB
4. 限定語言：不限

---

題目描述

給定一個二叉樹，每個節點上站一個人，節點數字表示父節點到該節點傳遞悄悄話需要的時間。初始時，根節點的人有一個悄悄話要傳遞給其他人。計算所有節點都接收到悄悄話的最長時間（即從根節點到最遠葉子節點的路徑時間和）。

輸入描述
一行整數序列，表示二叉樹的層序遍歷結果，-1表示空節點。例如：
0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2

輸出描述
一個整數，表示所有節點接收悄悄話的最長時間。例如輸入上述序列，輸出38（路徑0→20→7→3→2的時間總和）。

示例說明

• 輸入0 -1 10 -1 -1，輸出10（路徑0→10）。
• 輸入0 3 4 -1 -1 -1 -1，輸出4（路徑0→4）。

---

Java

問題分析

題目要求計算二叉樹中從根到最遠葉子節點的路徑時間和。每個節點的值表示父節點到該節點的傳遞時間，要求找到所有節點接收悄悄話的最長時間。

解題思路

1. 構建二叉樹：根據輸入的層序遍歷數組構建二叉樹結構，其中 -1 表示空節點。
2. 深度優先搜索 (DFS)：遍歷所有從根到葉子的路徑，計算路徑時間和的最大值。路徑和為路徑上所有節點值的總和（包括根節點）。

代碼實現

import java.util.*;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String line = sc.nextLine();Integer[] nums = parseInput(line);TreeNode root = buildTree(nums);int max = dfs(root, 0); // 計算路徑和（包含根節點）System.out.println(max);}// 將輸入字符串解析為 Integer 數組（處理 -1）private static Integer[] parseInput(String line) {String[] parts = line.split(" ");Integer[] nums = new Integer[parts.length];for (int i = 0; i < parts.length; i++) {if (parts[i].equals("-1")) {nums[i] = null;} else {nums[i] = Integer.parseInt(parts[i]);}}return nums;}// 構建層序二叉樹private static TreeNode buildTree(Integer[] nums) {if (nums == null || nums.length == 0 || nums[0] == null) return null;TreeNode root = new TreeNode(nums[0]);Queue<TreeNode> queue = new LinkedList<>();queue.add(root);int i = 1;while (!queue.isEmpty() && i < nums.length) {TreeNode node = queue.poll();// 處理左子節點if (i < nums.length && nums[i] != null) {node.left = new TreeNode(nums[i]);queue.add(node.left);}i++;// 處理右子節點if (i < nums.length && nums[i] != null) {node.right = new TreeNode(nums[i]);queue.add(node.right);}i++;}return root;}// DFS 計算從根到葉子的最大路徑和private static int dfs(TreeNode node, int currentSum) {if (node == null) return currentSum; // 空節點返回當前和currentSum += node.val; // 累加當前節點值if (node.left == null && node.right == null) {return currentSum; // 葉子節點返回總和}int leftSum = dfs(node.left, currentSum);int rightSum = dfs(node.right, currentSum);return Math.max(leftSum, rightSum);}
}

代碼解析

1. 輸入處理：
   • parseInput 將輸入字符串轉換為 Integer 數組，-1 轉為 null。
2. 構建二叉樹：
   • 使用隊列按層序處理每個節點的左右子節點，null 表示空節點。
3. DFS 計算路徑和：
   • 遞歸遍歷所有路徑，累加節點值，葉子節點返回路徑和，非葉子節點返回左右子樹的最大路徑和。

示例測試

1. 示例輸入：

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

   輸出：40
   解釋：路徑 0 → 20 → 15 → 3 → 2 的和為 0 + 20 + 15 + 3 + 2 = 40。

2. 測試用例1：
   輸入：

   0 -1 10 -1 -1
   

   輸出：10
   解釋：路徑 0 → 10 的和為 0 + 10 = 10。

3. 測試用例2：
   輸入：

   0 3 4 -1 -1 -1 -1
   

   輸出：4
   解釋：路徑 0 → 4 的和為 0 + 4 = 4。

綜合分析

1. 時間復雜度：O(n)
   • 構建二叉樹和 DFS 遍歷各需一次線性遍歷。
2. 空間復雜度：O(n)
   • 存儲二叉樹和遞歸棧空間。
3. 正確性保證：
   • DFS 確保遍歷所有路徑，取最大值邏輯正確。
4. 適用性：
   • 適用于題目約束（n ≤ 20000，節點值 ≤ 10000），能處理大規模輸入。

---

python

問題分析

題目要求計算從二叉樹根節點到最遠葉子節點的路徑時間和的最大值。每個節點的值表示父節點到該節點的傳遞時間。例如，路徑根節點→A→B的時間總和為父節點到A的時間加上A到B的時間。

解題思路

1. 構建二叉樹：根據輸入的層序遍歷數組構建二叉樹，其中 -1 表示空節點。
2. 深度優先搜索 (DFS)：遞歸計算所有從根到葉子的路徑時間和，取最大值。路徑和為路徑節點的值之和。

---

代碼實現

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef build_tree(level_order):"""根據層序遍歷數組構建二叉樹:param level_order: 層序數組，-1轉換為None:return: 根節點"""if not level_order or level_order[0] is None:return Noneroot