最新华为OD机试真题-K小姐的三叉搜索树(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🎧 K小姐的三叉搜索树
题目描述
K小姐正在学习数据结构,她了解到三叉搜索树的构造规则如下:
每个节点都存有一个数,当插入一个新的数时,从根节点向下寻找,直到找到一个合适的空节点插入。查找的规则是:
- 如果数小于节点的数减去 ,则将数插入节点的左子树。
- 如果数大于节点的数加上 ,则将数插入节点的右子树。
- 否则,将数插入节点的中子树。
现在,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(
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
最新华为OD机试-E+D卷 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测