页面加载中…
P3603. 计算三叉搜索树的高度
中等通过率 63% · 提交 347 · 通过 220
200分DFS2024E2025C树模拟
本题改编自华为 OD 机考真题方向 · 考点：200分 / DFS · 难度：中等
小慕正在设计一种特殊的，规则如下： 每个节点都存放一个数值。当插入一个新数时，从根节点开始向下查找，直到找到一个合适的空节点进行插入。 查找规则为： 1. 如果新数小于当前节点的数减去 500，则插入到当前节点的左子树； 2. 如果新数大于当前节点的数加上 500，则插入到当前节点的右子树； 3. 否则，插入到当前节点的中子树。 现在小慕有一系列数，请你按照上述规则，按顺序将这些数依次插入树中，构建出一棵三叉搜索树，最后输出这棵树的高度。
这类题属于华为 OD 机考真题方向中「200分 / DFS」方向的高频题型，通常考察对「200分 / DFS」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
提示：带虚线的词点一下有通俗解释。
输入描述
第一行为一个数 N，表示有 N 个数，1 <= N <= 10000 第二行为 N 个空格分隔的整数，每个数的范围为[1, 10000]
输出描述
输出树的高度(根节点的高度为 1)
示例
示例 1
输入示例
9 5000 2000 5000 8000 1800 7500 4500 1400 8100
输出示例
4
示例 2
输入示例
3 5000 4000 3000
输出示例
3
示例 3
输入示例
5 5000 2000 5000 8000 1800
输出示例
3
时间限制 1000 ms · 内存限制 128 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
解题思路
这道题题面不长，但对于没有接触过搜索树概念的同学来说，可能是比较费解的。
节点的表示
本题的节点最好通过构建节点类 class Node 来表示。之所以使用节点类而非邻接表，是因为邻接表要求节点的值是唯一的。但在示例中显然节点的值不唯一，因此使用邻接表来建树并不方便。三叉树的节点类可以用如下代码表示：
三叉搜索树的节点插入过程（举例说明）
假设此时这棵三叉搜索树已经构建了一部分。譬如此时我们要往这棵树中插入值为 8100 的节点，其过程应为：
1. 从根节点 5000 出发，比较 5000 和 8100 之间的大小关系。8100 - 5000 > 500，故该节点应该位于根节点 5000 的右子树中。 2. 发现根节点 5000 的右节点 8000 已经存在，则进行递归，进一步比较 8000 和 8100 之间的大小关系。abs(8100 - 8000) <= 500，故该节点应该位于节点 8000 的中间子树中。 3. 发现节点 8000 的中间节点 7500 已经存在，则进行递归，进一步比较 7500 和 8100 之间的大小关系。8100 - 7500 > 500，故该节点应该位于节点 7500 的右子树中。 4. 发现节点 7500 的右节点为空，此时将值为 8100 的节点插入节点 7500 的右节点。这样就完成了搜索树的插入操作。
三叉搜索树的节点插入过程（递归三要素）
注意到上述每一步的过程都是类似的，显然可以用递归来实现。考虑递归三要素。
递归子问题
插入节点 insert_node 的值 insert_node.val 和当前节点 cur_node 的值 cur_node.val 比较。若：
insert_node.val - cur_node.val > 500，则插入节点insert_node应该位于当前节点cur_node的右子树的位置。若此时cur_node的右节点cur_node.right不为空，则对cur_node.right进行递归调用。insert_node.val - cur_node.val < -500，则插入节点insert_node应该位于当前节点cur_node的左子树的位置。若此时cur_node的左节点cur_node.left不为空，则对cur_node.left进行递归调用。abs(insert_node.val - cur_node.val) <= 500，则插入节点insert_node应该位于当前节点cur_node的中间子树的位置。若此时cur_node的中间节点cur_node.mid不为空，则对cur_node.mid进行递归调用。
递归终止条件
做完上述判断后，若当前节点 cur_node 的对应子节点为空，说明 insert_node 可以插入在 cur_node 的对应节点位置。插入完毕，递归终止。
递归入口
除了根节点，其他节点都要从根节点出发进行比较和判断，故递归入口为插入节点 insert_node 和根节点 root 进行比较。
想清楚上述过程之后，建树的大致框架就已经能够完成了。其代码如下：
上述过程的单次时间复杂度为 O(log n)，由于对于的每一个新插入的 val 都必须调用上述函数。
计算树的高度
注意本题的设问是计算树的高度。这个问题有两种解决方案，同学们可以自行选择自己喜欢的方案来进行。在效率上，前者是略微优于后者的，因此后者需要在建树结束之后，对整棵树再做一次时间复杂度为 O(n) 的遍历，但总时间复杂度不变。
在建树过程中计算树的高度
可以在递归函数中多维护一个变量 cur_depth 表示当前节点 cur_node 的深度，同时维护一个全局变量 ans 表示全局的最大深度，一边建树一边同时更新当前树的最大高度。
在对子节点进行递归调用时，由于子节点的高度始终比当前节点大 1，所以应该将 cur_depth + 1 作为子节点的高度传入递归函数中。
在递归终止即进行节点插入时，进行 ans 和 cur_depth + 1 的比较。之所以是 cur_depth + 1，是因为进行节点插入后，该节点插入后的高度应该比当前节点高度 + 1。故 dfs() 递归函数可以修改为：
在建树完毕后计算树的高度
同样使用递归完成。其过程类似于 经典题型. 二叉树的最大深度。其核心的递归函数代码如下：
代码
解法一：建树过程中计算树的高度
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
