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

华为OD机试 - 二维伞的雨滴效应（Python/JS/C/C++ 2024 E卷 200分）

news 来源：原创 2024/9/19 8:18:19

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

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

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

在这里插入图片描述

二、输入描述

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

三、输出描述

输出如下三个值，以空格分割：是否是二叉排序树，左侧地面呈现的伞坠数字值，右侧地面呈现的伞坠数字值。
若是二叉排序树，则输出1，否则输出0。

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

四、测试用例

1、输入

6 4 3 5 8 7 9 10

2、输出

1 3 10

3、说明

6 4 3 5 8 7 9 10能够组成一个二叉搜索树，输出左侧地面呈现的伞坠数字值3，右侧地面呈现的伞坠数字值10。

五、解题思路

二叉搜索树又称二叉排序树，具有以下性质：

  1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
  2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
  3. 它的左右子树也分别为二叉搜索树；

二叉搜索树就不能插入重复的元素了，且每次插入都是插入到叶子节点的位置。

插入的元素比当前位置元素小就往左走，比当前位置元素大就往右走，直到为空。

六、Python算法源码

class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = Nonedef main():arr = list(map(int, input().split()))  # 输入节点值root = TreeNode(arr[0])  # 第一个节点为根节点deque = []  # 模拟双端队列deque.append(root)pre_node = TreeNode(-1)  # 当前节点的前一个节点flag = True  # 是否满足二叉搜索树属性# 判断并构造二叉搜索树for i in range(1, len(arr)):node = deque[-1]current_node = TreeNode(arr[i])# 前一个节点的值小于当前节点的值while deque and deque[-1].value < current_node.value:node = deque.pop()if deque:pre_node = deque[-1]# 小的值放在左子树if node.value < current_node.value:node.right = current_nodepre_node = nodeelse:# 不满足二叉搜索树属性直接跳出if current_node.value < pre_node.value:flag = Falsebreaknode.left = current_nodedeque.append(current_node)# 如果满足二叉搜索树特性，获取左子树的最左节点，右子树的最右节点if flag:left_node = rootwhile left_node.left or left_node.right:if left_node.left:left_node = left_node.leftelse:left_node = left_node.rightright_node = rootwhile right_node.left or right_node.right:if right_node.right:right_node = right_node.rightelse:right_node = right_node.leftprint(f"1 {0 if left_node.value == root.value else left_node.value} {0 if right_node.value == root.value else right_node.value}")else:print("0 0 0")if __name__ == "__main__":main()

七、JavaScript算法源码

class TreeNode {constructor(value) {this.value = value;  // 节点的值this.left = null;    // 左子节点this.right = null;   // 右子节点}
}function main() {// 读取输入，将输入的字符串按空格分割，并转换为数字数组const input = prompt("Enter node values:").trim().split(" ").map(Number);const root = new TreeNode(input[0]); // 第一个节点为根节点const deque = []; // 用数组模拟双端队列deque.push(root); // 将根节点加入队列let preNode = new TreeNode(-1); // 当前节点的前一个节点，初始化为值为 -1 的节点let flag = true; // 是否满足二叉搜索树属性// 遍历输入数组，构造二叉搜索树for (let i = 1; i < input.length; i++) {let node = deque[deque.length - 1];  // 获取队列的最后一个节点，作为当前节点的前一个节点const currentNode = new TreeNode(input[i]); // 创建当前节点// 当队列不为空且前一个节点的值小于当前节点的值时while (deque.length > 0 && deque[deque.length - 1].value < currentNode.value) {node = deque.pop(); // 从队列中移除并获取最后一个节点if (deque.length > 0) {preNode = deque[deque.length - 1]; // 更新前一个节点}}// 当前节点的值大于前一个节点的值，添加到右子树if (node.value < currentNode.value) {node.right = currentNode; // 设置右子节点preNode = node; // 更新前一个节点} else {// 如果当前节点的值小于前一个节点的值，不满足二叉搜索树属性，设置 flag 为 false 并退出循环if (currentNode.value < preNode.value) {flag = false;break;}node.left = currentNode; // 设置左子节点}deque.push(currentNode); // 将当前节点加入队列}// 如果满足二叉搜索树特性，获取左子树的最左节点和右子树的最右节点if (flag) {let leftNode = root; // 从根节点开始while (leftNode.left !== null || leftNode.right !== null) {leftNode = leftNode.left !== null ? leftNode.left : leftNode.right; // 找到最左边的节点}let rightNode = root; // 从根节点开始while (rightNode.left !== null || rightNode.right !== null) {rightNode = rightNode.right !== null ? rightNode.right : rightNode.left; // 找到最右边的节点}// 输出结果，1 表示符合二叉搜索树，输出左子树的最左节点和右子树的最右节点的值console.log(`1 ${leftNode.value === root.value ? 0 : leftNode.value} ${rightNode.value === root.value ? 0 : rightNode.value}`);} else {// 如果不满足二叉搜索树特性，输出 "0 0 0"console.log("0 0 0");}
}main(); // 调用主函数

八、C算法源码

#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点结构
typedef struct TreeNode {int value;  // 节点的值struct TreeNode *left;  // 左子节点struct TreeNode *right; // 右子节点
} TreeNode;// 创建新节点
TreeNode* createNode(int value) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); // 分配内存newNode->value = value;  // 设置节点值newNode->left = NULL;    // 初始化左子节点为空newNode->right = NULL;   // 初始化右子节点为空return newNode;
}// 将节点压入栈
void push(TreeNode** stack, int* size, TreeNode* node) {stack[(*size)++] = node;
}// 从栈中弹出节点
TreeNode* pop(TreeNode** stack, int* size) {return stack[--(*size)];
}// 获取栈顶节点
TreeNode* peek(TreeNode** stack, int size) {return stack[size - 1];
}int main() {int n, i, flag = 1;scanf("%d", &n); // 读取输入的节点数量int arr[n];for (i = 0; i < n; i++) {scanf("%d", &arr[i]); // 读取每个节点的值}TreeNode* root = createNode(arr[0]); // 第一个节点为根节点TreeNode* stack[1000]; // 模拟栈int stackSize = 0;push(stack, &stackSize, root); // 将根节点压入栈TreeNode* preNode = createNode(-1); // 当前节点的前一个节点，初始化为 -1for (i = 1; i < n; i++) {TreeNode* node = peek(stack, stackSize); // 获取栈顶节点TreeNode* currentNode = createNode(arr[i]); // 创建当前节点// 当栈不为空且栈顶节点的值小于当前节点的值时while (stackSize > 0 && peek(stack, stackSize)->value < currentNode->value) {node = pop(stack, &stackSize); // 弹出栈顶节点if (stackSize > 0) {preNode = peek(stack, stackSize); // 更新前一个节点}}// 当前节点的值大于前一个节点的值，添加到右子树if (node->value < currentNode->value) {node->right = currentNode; // 设置右子节点preNode = node; // 更新前一个节点} else {// 如果当前节点的值小于前一个节点的值，不满足二叉搜索树属性，设置 flag 为 0 并退出循环if (currentNode->value < preNode->value) {flag = 0;break;}node->left = currentNode; // 设置左子节点}push(stack, &stackSize, currentNode); // 将当前节点压入栈}// 如果满足二叉搜索树特性，获取左子树的最左节点和右子树的最右节点if (flag) {TreeNode* leftNode = root; // 从根节点开始while (leftNode->left != NULL || leftNode->right != NULL) {leftNode = (leftNode->left != NULL) ? leftNode->left : leftNode->right; // 找到最左边的节点}TreeNode* rightNode = root; // 从根节点开始while (rightNode->left != NULL || rightNode->right != NULL) {rightNode = (rightNode->right != NULL) ? rightNode->right : rightNode->left; // 找到最右边的节点}// 输出结果，1 表示符合二叉搜索树，输出左子树的最左节点和右子树的最右节点的值printf("1 %d %d\n", (leftNode->value == root->value ? 0 : leftNode->value),(rightNode->value == root->value ? 0 : rightNode->value));} else {// 如果不满足二叉搜索树特性，输出 "0 0 0"printf("0 0 0\n");}return 0;
}

九、C++算法源码

#include <iostream>
#include <deque>
#include <string>
#include <sstream>using namespace std;// 定义二叉树节点结构
struct TreeNode {int value; // 节点的值TreeNode* left;  // 左子节点TreeNode* right; // 右子节点// 构造函数初始化节点值和左右子节点TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};int main() {string input;getline(cin, input);  // 读取一整行输入，将其存储在 `input` 字符串中istringstream ss(input);  // 使用 `istringstream` 解析输入字符串int num;ss >> num;  // 读取第一个数字作为根节点的值TreeNode* root = new TreeNode(num);  // 创建根节点deque<TreeNode*> deque;  // 使用双端队列来存储节点，模拟栈deque.push_back(root);  // 将根节点加入队列TreeNode* preNode = new TreeNode(-1);  // 当前节点的前一个节点，初始化为值为 -1 的节点bool flag = true;  // 用于判断是否满足二叉搜索树属性// 逐个读取输入的剩余数字，构造二叉搜索树while (ss >> num) {TreeNode* node = deque.back();  // 获取队列的最后一个节点，作为当前节点的前一个节点TreeNode* currentNode = new TreeNode(num);  // 创建当前节点// 当队列不为空且队列末尾节点的值小于当前节点的值while (!deque.empty() && deque.back()->value < currentNode->value) {node = deque.back();  // 更新当前节点为队列末尾节点deque.pop_back();  // 从队列中移除末尾节点if (!deque.empty()) {preNode = deque.back();  // 更新前一个节点为队列新的末尾节点}}// 如果当前节点的值大于前一个节点的值，添加到右子树if (node->value < currentNode->value) {node->right = currentNode;  // 设置右子节点preNode = node;  // 更新前一个节点} else {// 如果当前节点的值小于前一个节点的值，不满足二叉搜索树属性if (currentNode->value < preNode->value) {flag = false;  // 设置 flag 为 false，表示不满足二叉搜索树break;  // 退出循环}node->left = currentNode;  // 设置左子节点}deque.push_back(currentNode);  // 将当前节点加入队列}// 如果满足二叉搜索树特性，获取左子树的最左节点和右子树的最右节点if (flag) {TreeNode* leftNode = root;  // 从根节点开始while (leftNode->left != nullptr || leftNode->right != nullptr) {// 找到最左边的节点leftNode = (leftNode->left != nullptr) ? leftNode->left : leftNode->right;}TreeNode* rightNode = root;  // 从根节点开始while (rightNode->left != nullptr || rightNode->right != nullptr) {// 找到最右边的节点rightNode = (rightNode->right != nullptr) ? rightNode->right : rightNode->left;}// 输出结果，1 表示符合二叉搜索树，输出左子树的最左节点和右子树的最右节点的值cout << "1 " << (leftNode->value == root->value ? 0 : leftNode->value) << " " << (rightNode->value == root->value ? 0 : rightNode->value) << endl;} else {// 如果不满足二叉搜索树特性，输出 "0 0 0"cout << "0 0 0" << endl;}return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

在这里插入图片描述

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 【新手上路】衡石分析平台使用手册-租户管理
  • 硬件看门狗导致MCU启动时间慢
  • Flask-JWT-Extended登录验证
  • python基础（1）pyenv安装和对Django使用
  • Python 入门教程（4）数据类型 | 4.5、字符串类型
  • Scala尾递归解决爆栈问题
  • Python VS Golng 谁更胜一筹？
  • 智能化技术在灌区管理中的应用前景
  • 开源模型应用落地-qwen模型小试-调用Qwen2-VL-7B-Instruct-更清晰地看世界-集成vLLM（二）
  • AI教你学Python 第12天 ： Lambda 表达式
  • Vue3使用shapefile读取矢量数据，以数组形式返回坐标点
  • [SDX35+WCN6856]SDX35 + WCN6856 WiFi导致系统crash问题分析及解决方案
  • .Net Core 生成管理员权限的应用程序
  • Linux--守护进程与会话
  • Open3D 特征点匹配（Python）
  • .pyc 想到的一些问题
  • Angular6错误 Service: No provider for Renderer2
  • const let
  • ES6语法详解(一)
  • GitUp, 你不可错过的秀外慧中的git工具
  • Java基本数据类型之Number
  • Leetcode 27 Remove Element
  • MyEclipse 8.0 GA 搭建 Struts2 + Spring2 + Hibernate3 （测试）
  • vue学习系列（二）vue-cli
  • 从零开始学习部署
  • 第13期 DApp 榜单 ：来，吃我这波安利
  • 对象管理器（defineProperty）学习笔记
  • 更好理解的面向对象的Javascript 1 —— 动态类型和多态
  • 记一次删除Git记录中的大文件的过程
  • 前端性能优化——回流与重绘
  • 使用agvtool更改app version／build
  • 使用putty远程连接linux
  • 微信开源mars源码分析1—上层samples分析
  • 学习笔记DL002:AI、机器学习、表示学习、深度学习，第一次大衰退
  • 阿里云服务器购买完整流程
  • ​2021半年盘点，不想你错过的重磅新书
  • ​LeetCode解法汇总2304. 网格中的最小路径代价
  • (2009.11版)《网络管理员考试 考前冲刺预测卷及考点解析》复习重点
  • (4) openssl rsa/pkey(查看私钥、从私钥中提取公钥、查看公钥)
  • （C语言）球球大作战
  • (delphi11最新学习资料) Object Pascal 学习笔记---第8章第2节（共同的基类）
  • （Redis使用系列） SpringBoot 中对应2.0.x版本的Redis配置 一
  • （十）DDRC架构组成、效率Efficiency及功能实现
  • （数据大屏）（Hadoop）基于SSM框架的学院校友管理系统的设计与实现+文档
  • (转)h264中avc和flv数据的解析
  • .NET 4.0中的泛型协变和反变
  • .NET LINQ 通常分 Syntax Query 和Syntax Method
  • .NET下的多线程编程—1-线程机制概述
  • @PostConstruct 注解的方法用于资源的初始化
  • [ACTF2020 新生赛]Include
  • [Android 数据通信] android cmwap接入点
  • [codevs 2822] 爱在心中 【tarjan 算法】
  • [HackMyVM]靶场 VivifyTech
  • [HITCON 2017]SSRFme perl语言的 GET open file 造成rce
  • [HNOI2006]鬼谷子的钱袋