【最新华为OD机试E卷】计算三叉搜索树的高度(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目正在持续上线中~

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🌲 计算三叉搜索树的高度

题目描述

K小姐正在学习数据结构，她了解到三叉搜索树的构造规则如下：

每个节点都存有一个数，当插入一个新的数时，从根节点向下寻找，直到找到一个合适的空节点插入。查找的规则是：

1. 如果数小于节点的数减去 ，则将数插入节点的左子树。
2. 如果数大于节点的数加上 ，则将数插入节点的右子树。
3. 否则，将数插入节点的中子树。

现在，K小姐有一系列数，请按以上规则，按顺序将数插入树中，构建出一棵三叉搜索树，最后输出树的高度。

输入格式

第一行为一个正整数 ，表示有 个数，。

第二行为 个空格分隔的正整数，每个数的范围为 。

输出格式

输出树的高度（根节点的高度为 ）。

样例输入1

5
5000 2000 5000 8000 1800

样例输出1

3

样例解释

样例输入2

3
5000 4000 3000

样例输出2

3

样例解释

样例输入3

9
5000 2000 5000 8000 1800 7500 4500 1400 8100

样例输出3

4

数据范围

每个数

题解

模拟

这道题目要求我们实现一个特殊的三叉搜索树，并计算其高度。

让我们一步步来分析这个问题：

首先，需要理解这个特殊的三叉搜索树的插入规则。

与普通的二叉搜索树不同，这里的每个节点有三个子节点：左子节点、中子节点和右子节点。插入规则基于当前节点值与待插入值之间的差值。

可以定义一个 Node 类来表示树的节点，每个节点包含一个值和三个子节点指针。

插入操作 是这个问题的核心。从根节点开始，根据插入规则递归地向下寻找合适的位置插入新节点。

在插入过程中，可以同时记录当前节点的深度。每次递归调用时，深度加一。我们用一个全局变量来记录最大深度，这就是树的高度。

• 时间复杂度分析：对于每个输入的数，我们最坏情况下需要遍历整棵树的高度。如果树是平衡的，高度约为 ，其中 是节点数。所以总的时间复杂度是 。在最坏情况下（树完全不平衡），时间复杂度可能达到 。

• 空间复杂度：我们需要存储所有的节点，所以空间复杂度是 。

参考代码

• Python

class Node:
    def __init__(self, val):
        self.val = val  # 节点的值
        self.left = None  # 左子节点
        self.right = None  # 右子节点
        self.mid = None  # 中子节点

def insert(root, val, depth):
    global max_depth
    max_depth = max(max_depth, depth)  # 更新最大深度
    if root is None:
        return Node(val)  # 如果当前节点为空，创建新节点
    if val < root.val - 500:
        root.left = insert(root.left, val, depth + 1)  # 插入左子树
    elif val > root.val + 500:
        root.right = insert(root.right, val, depth + 1)  # 插入右子树
    else:
        root.mid = insert(root.mid, val, depth + 1)  # 插入中子树
    return root

n = int(input())  # 读取输入的数字个数
nums = list(map(int, input().split()))  # 读取所有数字
max_depth = 0  # 初始化最大深度
root = None  # 初始化根节点
for num in nums:
    root = insert(root, num, 1)  # 插入每个数字
print(max_depth)  # 输出树的高度

• C

#include <stdio.h>
#include <stdlib.h>

// 定义树节点结构
typedef struct Node {
    int val;
    struct Node *left, *right, *mid;
} Node;

int max_depth = 0;  // 全局变量，记录最大深度

// 创建新节点
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->left = node->right = node->mid = NULL;
    return node;
}

// 插入节点并更新最大深度
Node* insert(Node* root, int val, int depth) {
    if (depth > max_depth) max_depth = dept