华为 OD 机试：二维伞雨滴效应的 BST 验证与实现

二维伞的雨滴效应解题思路

问题背景

在华为 OD 机试中，这类题目通常考察对数据结构特性的理解。所谓的'二维伞'，本质上是一个二叉搜索树（BST）。雨滴落在伞面流到伞坠的过程，对应着树中数据的流向。我们需要完成两个任务：一是判断给定的正整数序列是否合法地构成了一个 BST 的前序遍历；二是如果合法，找出这棵树最左侧和最右侧的叶子节点数值。

核心逻辑分析

要解决这个问题，不能直接暴力枚举。我们需要利用 BST 的性质：左子树所有节点小于根，右子树所有节点大于根。

1. 验证前序遍历合法性

前序遍历的顺序是'根 - 左 - 右'。验证时，我们可以维护一个栈来记录当前路径上的节点。每当遇到比栈顶小的元素，说明进入了左子树；如果遇到比栈顶大的元素，需要回溯父节点，直到找到合适的插入位置。这个过程可以在 O(N) 时间内完成。

2. 提取'伞坠'信息

题目中的'伞坠'实际上指的是叶子节点。由于是二叉搜索树，最左侧的伞坠对应中序遍历的第一个叶子，最右侧对应最后一个叶子。为了准确获取，我们可以在验证通过后，根据前序序列重建这棵树（或模拟构建过程），然后分别寻找最左和最右的叶子。

代码实现

下面给出完整的 JavaScript 实现。注意处理边界情况，比如数组为空或只有一个元素的情况。

function solve(preorder) {
  if (!preorder || preorder.length === 0) return [0]; // 非法

  let isValid = true;
  let root = null;

  // 这里使用递归方式构建树并验证，逻辑更直观
  function buildTree(index, min, max) {
    if (index[0] >= preorder.length) return null;
    
    const val = preorder[index[0]];
    if (val < min || val > max) return null;

    index[0]++;
    const node = { val };
    node.left = buildTree(index, min, val);
    node.right = buildTree(index, val, max);
    return node;
  }

  const idx = [0];
  root = buildTree(idx, -Infinity, Infinity);

  // 如果构建过程中没有消耗完所有节点，或者树结构不完整导致剩余节点无法匹配，则视为非法
  if (idx[0] !== preorder.length) {
    isValid = false;
  }

  if (!isValid) return [0];

  // 寻找最左和最右叶子
  let leftLeaf = null;
  let rightLeaf = null;

  function findLeaves(node) {
    if (!node) return;
    if (!node.left && !node.right) {
      if (!leftLeaf) leftLeaf = node.val;
      rightLeaf = node.val; // 每次更新都会覆盖，最后即为最右
    }
    findLeaves(node.left);
    findLeaves(node.right);
  }

  findLeaves(root);

  return [1, leftLeaf, rightLeaf];
}

调试与注意事项

在实际提交时，记得处理输入输出的格式转换。有些测试用例可能包含重复值，但 BST 定义通常不包含重复键，需确认题目要求。另外，单节点树也是合法的，此时左右伞坠为同一个值。

总结

这道题的关键在于将抽象的物理模型映射回标准的数据结构操作。掌握 BST 的验证方法，配合简单的树遍历，就能轻松拿下。