华为OD机试真题 Java 实现【二维伞的雨滴效应】【2023 B卷 100分】，附详细解题思路

大家好，我是哪吒。

做技术，我是认真的，立志于打造最权威的华为OD机试真题专栏，帮助那些与我有同样需求的人（考华为OD机试，升职加薪），每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

华为OD机试（JAVA）真题（A卷+B卷）

一、题目描述

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

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

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

二、输入描述

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

三、输出描述

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

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

四、解题思路

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

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

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

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

五、Java算法源码

package com.guor.od;import java.util.Scanner;import java.util.*;public class OdTest01 {        public static void main(String[] args) {        Scanner in = new Scanner(System.in);        // 输入的节点值        int[] arr = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();        // 第一个节点为根节点        Treenode root = new TreeNode(arr[0]);        // 保存节点        Deque deque = new ArrayDeque();        // 加入根节点        deque.push(root);        // 当前节点的前一个节点        TreeNode preNode = new TreeNode(-1);        // 是否满足二叉搜索树属性        boolean flag = true;        // 判断并构造二叉搜索树        for (int i = 1; i < arr.length; i++) {            // 当前节点的前一个节点            TreeNode node = deque.peekLast();            // 当前节点            TreeNode currentNode = new TreeNode(arr[i]);            // 前一个节点的值小于当前节点的值            while (!deque.isEmpty() && deque.peekLast().value < currentNode.value) {                node = deque.removeLast();                // 如果队列不为空，更新前一个节点值                if (!deque.isEmpty()) {                    preNode = deque.peekLast();                }            }            // 小的值放在左子树            if (node.value < currentNode.value) {                node.right = currentNode;                preNode = node;            } else {                // 不满足二叉搜索树属性直接跳出                if (currentNode.value < preNode.value) {                    flag = false;                    break;                }                // 大的值放在右子树                node.left = currentNode;            }            // 将当前的值加入队列            deque.addLast(currentNode);        }        // 如果满足二叉搜索树特性，获取左子树的最左节点，右子树的最右节点        if (flag) {            TreeNode leftNode = root;            while (leftNode.left != null || leftNode.right != null) {                if (leftNode.left != null) {                    leftNode = leftNode.left;                } else {                    leftNode = leftNode.right;                }            }            TreeNode rightNode = root;            while (rightNode.left != null || rightNode.right != null) {                if (rightNode.right != null) {                    rightNode = rightNode.right;                } else {                    rightNode = rightNode.left;                }            }            // 1 表示符合二叉搜索树            // leftNode 左侧地面呈现的伞坠数字值            // rightNode 右侧地面呈现的伞坠数字值            StringBuilder builder = new StringBuilder();            builder.append(1).append(" ")                    .append(leftNode.value == root.value ? 0 : leftNode.value).append(" ")                    .append(rightNode.value == root.value ? 0 : rightNode.value);            System.out.println(builder);        } else {            // 不符合二叉搜索树时直接输出0            System.out.println("0 0 0");        }        return;    }    // 定义一棵树    static class TreeNode {        private int value;        private TreeNode left;        private TreeNode right;        public TreeNode(int value) {            this.value = value;        }    }}

六、效果展示

1、输入

6 4 3 5 8 7 9 10

2、输出

1 3 10

3、说明

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

🏆下一篇：华为OD机试真题 Java 实现【跳房子II】【2023 B卷 100分】，附详细解题思路

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，发现新题目，随时更新，全天CSDN在线答疑。

来源地址：https://blog.csdn.net/guorui_java/article/details/131657550