当前位置：首页 > news >正文

华为OD 二维伞的雨滴效应

news 2025/7/8 13:06:13

1. 题目描述

普通的伞在二维平面世界中，左右两侧均有一条边，而两侧伞边最下面各有一个伞坠子，雨滴落到伞面，逐步流到伞坠处，会将伞坠的信息携带并落到地面，随着日积月累，地面会呈现伞坠的信息。

1、为了模拟伞状雨滴效应，用二叉树来模拟二维平面伞(如下图所示)，现在输入一串正整数数组序列(不含0，数组成员至少是1个) ，若此数组序列是二叉搜索树的前序遍历的结果，那么请输出一个返回值1，否则输出0.

2、同时请将此序列构成的伞状效应携带到地面的数字信息输出来(左边伞坠信息，右边伞坠信息，详细参考示例图地面上数字)，若此树不存在左或右扇坠，则对应位置返回0。同时若非二叉排序树那么左右伞坠信息也返回0。

在这里插入图片描述

输入描述:

1个通过空格分割的整数序列字符串，数组不含0，数组成员至少1个，输入的数组的任意两个数字都互不相同，最多1000个正整数，正整数值范围1~65535。

输出描述:

输出如下三个值，以空格分隔: 是否二叉排序树，左侧地面呈现的伞坠数字值，右侧地面呈现的伞坠数字值.

若是二叉排序树，则输出1，否则输出0 (其左右伞坠值也直接赋值0) 。

若不存存在左侧或者右侧伞坠值，那么对应伞坠值直接赋值0。

示例1

输入:

8 3 1 6 4 7 10 14 13

输出:

1 1 13

说明:

1表示是二叉搜索树前序遍历结果，1表示左侧地面呈现的伞坠数字值，13表示右侧地面呈现的伞坠数字值

2. 题解

这个题目个人觉得比较难。

这个题目首先是一个二叉树的题目。首先，我们需要判断它是不是一颗二叉排序树。

如果是，需要根据二叉排序树的前序遍历序列重建这个树；

其次我们需要理解题目中的伞坠是什么意思？

根据样例我们猜，其实：

左伞坠就是左子树中最左下位置的叶子节点
右伞坠就是右子树中最右下位置的叶子节点

如果你比较有灵性，你会发现右伞坠其实就是最后一个节点（中序遍历的最后一个节点）。

首先判断是否是二叉排序树的前序序列；

首先取首节点作为根节点的值，往右找到第一个大于首节点的下标first_gt_idx；从first_gt_idx一直到序列末尾，我们需要校验这些值是否都大于root_val。校验完成后，再递归调用处理左右两颗子树。

下面是图解

在这里插入图片描述
判断是否是二叉搜索树和重建树的逻辑是一样的。

树建好后，再处理左右伞坠就行了。

至此，我们就可以写出代码了。

#include <iostream>
#include <string>
#include <vector>
#include <cctype>using namespace std;
struct node {node( node *l_, node *r_, int v_):l(l_),r(r_),v(v_) {}node *l{};node *r{};int v{};
};node *build_bst_tree(const vector<int> &a, int l, int r) {if ( l > r)return nullptr;node *rt = new node(nullptr, nullptr, a[l]);int rbg = l + 1;while ( rbg < r + 1 && a[rbg] < a[l]) {++rbg;}rt->l = build_bst_tree( a, l + 1, rbg - 1);rt->r = build_bst_tree( a, rbg, r);return rt;
}bool is_bst_preorder( const vector<int> &a, int l, int r)
{if ( l >= r)return true;int rt_val = a[l];int rbg = l + 1;while ( rbg < r + 1 && a[rbg] < rt_val) {++rbg;}for (int i = rbg; i < r + 1; ++i) {if ( a[i] <= rt_val)return false;}return is_bst_preorder( a, l + 1, rbg - 1) && is_bst_preorder( a, rbg, r);
}
int main()
{string s;getline( cin, s);vector<int> a;int p = 0;int s_sz = s.size();while ( p < s_sz ) {if ( s[p] == ' ') {p++;continue;}string c;while ( p < s_sz && std::isdigit(s[p])) {c += s[p++];}a.emplace_back( std::stoi(c));}// for (auto &v: a) {//     cout << v << endl;// }int is_bst_pre = is_bst_preorder(a, 0, a.size() - 1) ? 1 : 0;int lfall{};int rfall{};if ( is_bst_pre ) {node *rt = build_bst_tree( a, 0, a.size() - 1);node *lnode = rt->l;node *rnode = rt->r;if ( rt->l && rt->r) {while ( lnode->l || lnode->r) {if ( lnode->l) {lnode = lnode->l;}else {lnode = lnode->r;}}while ( rnode->r || rnode->l) {if ( rnode->r ) {rnode = rnode->r;}else {rnode = rnode->l;}}lfall = lnode->v;rfall = rnode->v;}}cout << is_bst_pre << " " << lfall << " " << rfall << endl;return 0;
}