最新华为OD机试真题-K小姐的三叉搜索树(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

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

👏 感谢大家的订阅➕ 和 喜欢💗

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎在线评测链接

K小姐的三叉搜索树(100分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🎧 K小姐的三叉搜索树

题目描述

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

样例解释

数据范围

每个数

题解

我们可以使用递归的方式来构建三叉搜索树。对于每个节点，根据输入的数与节点的数的大小关系，决定将数插入左子树、右子树还是中子树。在插入过程中，记录树的最大高度。

参考代码

• 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(