2025 A卷 200分 题型
本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；
并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；
本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》
华为OD机试真题《二维伞的雨滴效应》：
文章快捷目录
题目描述及说明
Java
python
JavaScript
C
GO
题目名称：二维伞的雨滴效应
知识点：递归、二叉搜索树验证、逻辑处理
时间限制：1秒
空间限制：256MB
限定语言：不限
题目描述
普通的伞在二维平面世界中，左右两侧均有一条边，而两侧伞边最下面各有一个伞坠子。雨滴落到伞面后，逐步流到伞坠处，携带伞坠信息落到地面。现输入一串正整数数组序列（不含0，数组成员至少1个），要求：
- 判断该数组是否为二叉搜索树的前序遍历结果。若是，输出1；否则输出0。
- 若为二叉搜索树，输出左右伞坠信息（即树的最左端和最右端叶子节点值）；若无左/右伞坠，则对应位置输出0。若非二叉搜索树，左右伞坠信息均返回0。
输入示例
8 3 1 6 4 7 10 14 13
输出示例
1 1 13
说明
1表示是二叉搜索树前序遍历结果。1为左伞坠值（最左叶子节点值）。13为右伞坠值（最右叶子节点值）。
输入约束
- 输入数组任意两个数字互不相同。
- 数组长度最多1000，数值范围1~65535。
Java
问题分析
题目要求判断给定的正整数数组是否为二叉搜索树（BST）的前序遍历结果，并输出相应的结果。如果是BST，还需要找出最左和最右的叶子节点值（伞坠信息）。主要挑战在于如何高效验证前序遍历的正确性，并在验证的同时构建树结构以确定叶子节点。
解题思路
验证BST前序遍历：
- 递归检查数组是否符合BST前序遍历的结构。根节点后，找到第一个大于根的元素作为右子树的起点，确保右子树所有元素均大于根，左子树所有元素均小于根。
构建树结构：
- 如果验证通过，递归构建二叉树，以便后续查找叶子节点。
查找叶子节点：
- 前序遍历构建好的树，记录第一个和最后一个遇到的叶子节点值，即为最左和最右伞坠信息。
代码实现
import java.util.Scanner;
public class Main {
static int leftLeaf = 0;
static int rightLeaf = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
String[] parts = input.split(" ");
int[] preorder = new int[parts.length];
for (int i = 0; i < parts.length; i++) {
preorder[i] = Integer.parseInt(parts[i]);
}
boolean isBST = verifyBST(preorder, 0, preorder.length - 1);
if (isBST) {
TreeNode root = buildTree(preorder, 0, preorder.length - 1);
findLeaves(root);
System.out.println("1 " + leftLeaf + " " + rightLeaf);
} else {
System.out.println("0 0 0");
}
}
private static boolean verifyBST(int[] preorder, int start, int end) {
if (start > end) {
return true;
}
int rootVal = preorder[start];
int mid = end + 1;
for (int i = start + 1; i <= end; i++) {
if (preorder[i] > rootVal) {
mid = i;
break;
}
}
for (int i = mid; i <= end; i++) {
if (preorder[i] <= rootVal) {
return false;
}
}
boolean leftValid = verifyBST(preorder, start + 1, mid - 1);
boolean rightValid = verifyBST(preorder, mid, end);
return leftValid && rightValid;
}
private static TreeNode buildTree(int[] preorder, int start, int end) {
if (start > end) {
return null;
}
int rootVal = preorder[start];
TreeNode root = new TreeNode(rootVal);
if (start == end) {
return root;
}
int mid = end + 1;
for (int i = start + 1; i <= end; i++) {
if (preorder[i] > rootVal) {
mid = i;
break;
}
}
root.left = buildTree(preorder, start + 1, mid - 1);
root.right = buildTree(preorder, mid, end);
return root;
}
private static void findLeaves(TreeNode root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
if (leftLeaf == 0) {
leftLeaf = root.val;
}
rightLeaf = root.val;
}
findLeaves(root.left);
findLeaves(root.right);
}
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
}
代码详解
主函数：
- 读取输入并转换为整型数组。
- 调用
verifyBST验证数组是否为BST前序遍历。 - 验证通过后构建树，查找叶子节点并输出结果。
verifyBST函数：
- 递归检查数组区间是否符合BST结构。确定右子树起点，验证右子树所有元素大于根，递归检查左右子树。
buildTree函数：
- 递归构建树结构，确定左右子树区间并构建节点。
findLeaves函数：
- 前序遍历树，记录第一个和最后一个叶子节点值。
示例测试
示例1：
输入：8 3 1 6 4 7 10 14 13
输出：1 1 13
说明：验证通过，最左叶子为1，最右为13。
示例2：
输入：5 3 2 4 6 7
输出：1 2 7
说明：验证通过，最左叶子为2，最右为7。
示例3：
输入：5 3 6 2
输出：0 0 0
说明：右子树中出现2，验证失败。
综合分析
该方案通过递归高效地验证前序遍历的正确性，并在验证过程中确定树的结构。虽然时间复杂度为O(n²)，但对于题目约束（n≤1000）足够高效。构建树后，通过前序遍历快速找到叶子节点，确保了正确性和简洁性。递归深度可能引起栈溢出，但在合理约束下表现良好。
python
问题分析
题目要求判断给定的正整数数组是否为二叉搜索树（BST）的前序遍历结果，并输出相应的结果。如果是BST，还需要找出最左和最右的叶子节点值（伞坠信息）。主要挑战在于如何高效验证前序遍历的正确性，并在验证的同时构建树结构以确定叶子节点。
解题思路
验证BST前序遍历：
- 递归检查数组是否符合BST前序遍历的结构。根节点后，找到第一个大于根的元素作为右子树的起点，确保右子树所有元素均大于根，左子树所有元素均小于根。
构建树结构：
- 如果验证通过，递归构建二叉树，以便后续查找叶子节点。
查找叶子节点：
- 左伞坠是左子树的最左叶子节点，右伞坠是右子树的最右叶子节点。若左/右子树不存在，则对应伞坠为0。
代码实现
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def verify_bst(preorder, start, end):
if start > end:
return True
root_val = preorder[start]
mi