【独家OD2023C卷真题】20天拿下华为OD笔试【DFS】2023C-计算三叉搜索树的高度【欧弟算法】全网注释最详细分类最全的华为OD真题题解

2023-12-01 02:20
文章标签 算法 全网 独家 笔试 搜索 分类 华为 详细 真题 注释 dfs 20 题解 最全 od 拿下 欧弟 三叉 od2023c 2023c

本文主要是介绍【独家OD2023C卷真题】20天拿下华为OD笔试【DFS】2023C-计算三叉搜索树的高度【欧弟算法】全网注释最详细分类最全的华为OD真题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 题目描述与示例
    • **题目描述：**
    • **输入描述**
    • **输出描述**
    • **示例一**
      • **输入**
      • **输出**
      • **说明**
    • **示例二**
      • **输入**
      • **输出**
      • **说明**
    • **示例三**
      • **输入**
      • **输出**
      • **说明**
  • 解题思路
    • 节点的表示
    • 三叉搜索树的节点插入过程（举例说明）
    • 三叉搜索树的节点插入过程（递归三要素）
    • 计算树的高度
      • 在建树过程中计算树的高度
      • 在建树完毕后计算树的高度
  • 代码
    • 解法一：建树过程中计算树的高度
      • python
      • java
      • cpp
    • 解法二：建树完毕后计算树的高度
      • python
      • java
      • cpp
    • 时空复杂度
  • 华为OD算法/大厂面试高频题算法练习冲刺训练

题目描述与示例

题目描述：

定义构造三叉搜索树规则如下：

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

查找的规则是：

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

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

输入描述

第一行为一个数 N，表示有 N 个数，1 <= N <= 10000

第二行为 N 个空格分隔的整数，每个数的范围为[1, 10000]

输出描述

输出树的高度(根节点的高度为 1)

示例一

输入

5
5000 2000 5000 8000 1800

输出

3

说明

最终构造出的树如下，高度为 3：

在这里插入图片描述

示例二

输入

3
5000 4000 3000

输出

3

说明

最终构造出的树如下，高度为 3：

在这里插入图片描述

示例三

输入

9
5000 2000 5000 8000 1800 7500 4500 1400 8100

输出

4

说明

最终构造出的树如下，高度为 4：

在这里插入图片描述

解题思路

这道题题面不长，但对于没有接触过搜索树的概念的同学来说，可能是比较费解的。

节点的表示

本题的节点最好通过构建节点类class Node来表示。之所以使用节点类而非邻接表，是因为邻接表要求节点的值是唯一的。但在示例中显然节点的值不唯一，因此使用邻接表来建树并不方便。三叉树的节点类可以用如下代码表示：

# 构建树节点类
class Node:def __init__(self, val):self.val = valself.left = Noneself.mid  = Noneself.right = None

三叉搜索树的节点插入过程（举例说明）

假设此时这棵三叉搜索树已经构建了一部分。譬如

在这里插入图片描述

此时我们要往这棵树中插入值为8100的节点，其过程应为：

  1. 从根节点5000出发，比较5000和8100之间的大小关系。8100 - 5000 > 500，故该节点应该位于根节点5000的右子树中。

在这里插入图片描述

  1. 发现根节点5000的右节点8000已经存在，则进行递归，进一步比较8000和8100之间的大小关系。abs(8100 - 8000) <= 500，故该节点应该位于节点8000的中间子树中。

在这里插入图片描述

  1. 发现节点8000的中间节点7500已经存在，则进行递归，进一步比较7500和8100之间的大小关系。8100 - 7500 > 500，故该节点应该位于节点7500的右子树中。

在这里插入图片描述

  1. 发现节点7500的右节点为空，此时将值为8100的节点插入节点7500的右节点。这样就完成了搜索树的插入操作。

在这里插入图片描述

三叉搜索树的节点插入过程（递归三要素）

注意到上述每一步的过程都是类似的，显然可以用递归来实现。考虑递归三要素。

  1. 递归子问题
    • 插入节点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_mid.left不为空，则对cur_node.mid进行递归调用。
  2. 递归终止条件
    • 做完上述判断后，若当前节点cur_node的对应子节点为空，说明insert_node可以插入在cur_node的对应节点位置。插入完毕，递归终止。
  3. 递归入口
    • 除了根节点，其他节点都要从根节点出发进行比较和判断，故递归入口为插入节点insert_node和根节点root进行比较。

想清楚上述过程之后，建树的大致框架就已经能够完成了。其代码如下：

def dfs(cur_node, val):if cur_node.val - val < -500:if cur_node.left is None:cur_node.left = Node(val)returndfs(cur_node.left, val)elif cur_node.val - val > 500:if cur_node.right is None:cur_node.right = Node(val)returndfs(cur_node.right, val)else:if cur_node.mid is None:cur_node.mid = Node(val)returndfs(cur_node.mid, val)

上述过程的单次时间复杂度为O(logn)，由于对于的每一个新插入的val都必须调用上述

计算树的高度

注意本题的设问是计算树的高度。这个问题有两种解决方案，同学们可以自行选择自己喜欢的方案来进行。在效率上，前者是略微优于后者的，因此后者需要在建树结束之后，对整棵树再做一次时间复杂度为O(n)的遍历，但总时间复杂度不变。

在建树过程中计算树的高度

可以在递归函数中多维护一个变量cur_depth表示当前节点cur_node的深度，同时维护一个全局变量ans表示全局的最大深度，一边建树一遍同时更新当前树的最大高度。

在对子节点进行递归调用时，由于子节点的高度始终比当前节点大1，所以应该将cur_depth+1作为子节点的高度传入递归函数中。

在递归终止即进行节点插入时，进行ans和cur_depth+1的比较。之所以是cur_depth+1，是因为进行节点插入后，该节点插入后的高度应该比当前节点高度+1。故dfs()递归函数可以修改为

def dfs(cur_node, val, cur_depth):global ansif cur_node.val - val < -500:if cur_node.left is None:cur_node.left = Node(val)ans = max(ans, cur_depth + 1)returndfs(cur_node.left, val, cur_depth + 1)elif cur_node.val - val > 500:if cur_node.right is None:cur_node.right = Node(val)ans = max(ans, cur_depth + 1)returndfs(cur_node.right, val, cur_depth + 1)else:if cur_node.mid is None:cur_node.mid = Node(val)ans = max(ans, cur_depth + 1)returndfs(cur_node.mid, val, cur_depth + 1)

在建树完毕后计算树的高度

同样使用递归完成。其过程类似于LeetCode104. 二叉树的最大深度。其核心的递归函数代码如下

def dfs_cal_height(node, cur_depth):if node == None:returnglobal ansans = max(cur_depth, ans)dfs_cal_height(node.left, cur_depth+1)dfs_cal_height(node.mid, cur_depth+1)dfs_cal_height(node.right, cur_depth+1)

代码

解法一：建树过程中计算树的高度

python

# 题目：【DFS】2023C-计算三叉搜索树的高度
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：DFS/树（解法一：建树过程中计算树的高度）
# 代码看不懂的地方，请直接在群上提问# 构建树节点类
class Node:def __init__(self, val):self.val = valself.left = Noneself.mid = Noneself.right = None# 创建dfs函数，用于对树插入值为val的节点
# 参数cur_node表示与val进行比较的当前节点
# 参数cur_depth表示当前深度
def dfs(cur_node, val, cur_depth):global ans# 插入节点insert_node位于当前节点cur_node左子树的情况if cur_node.val - val < -500:# 若cur_node的左节点不存在，则新建插入节点# insert_node = Node(val)# 并将其插入cur_node的左节点中if cur_node.left is None:cur_node.left = Node(val)# 插入该节点后，最终深度为当前深度+1，故ans应该与cur_depth+1进行比较ans = max(ans, cur_depth + 1)return# 否则对左节点进行递归调用，继续比较，同时深度+1dfs(cur_node.left, val, cur_depth + 1)# 插入节点insert_node位于当前节点cur_node右子树的情况elif cur_node.val - val > 500:# 若cur_node的右节点不存在，则新建插入节点# insert_node = Node(val)# 并将其插入cur_node的右节点中if cur_node.right is None:cur_node.right = Node(val)# 插入该节点后，最终深度为当前深度+1，故ans应该与cur_depth+1进行比较ans = max(ans, cur_depth + 1)return# 否则对右节点进行递归调用，继续比较，同时深度+1dfs(cur_node.right, val, cur_depth + 1)# 插入节点insert_node位于当前节点cur_node中间子树的情况else:# 若cur_node的终极那节点不存在，则新建插入节点# insert_node = Node(val)# 并将其插入cur_node的中间节点中if cur_node.mid is None:cur_node.mid = Node(val)# 插入该节点后，最终深度为当前深度+1，故ans应该与cur_depth+1进行比较ans = max(ans, cur_depth + 1)return# 否则对中间节点进行递归调用，继续比较，同时深度+1dfs(cur_node.mid, val, cur_depth + 1)# 输入节点数目n
n = int(input())
# 输入节点值数组vals
vals = list(map(int, input().split()))
# 构建根节点，根节点的值一定为vals数组中的第一个元素
root = Node(vals[0])
# 答案变量
ans = 1
# 遍历除了根节点以外的其他节点的值val
# 这个值对应插入节点insert_node
for val in vals[1:]:# 对于每一个节点的值val，都调用dfs函数# 递归入口传入根节点root，插入新的值为val的节点# 当前深度为1dfs(root, val, 1)print(ans)

java

import java.util.Scanner;class Node {int val;Node left, mid, right;Node(int val) {this.val = val;this.left = null;this.mid = null;this.right = null;}
}public class Main {static int ans = 1;static void dfs(Node curNode, int val, int curDepth) {if (curNode.val - val < -500) {if (curNode.left == null) {curNode.left = new Node(val);ans = Math.max(ans, curDepth + 1);return;}dfs(curNode.left, val, curDepth + 1);} else if (curNode.val - val > 500) {if (curNode.right == null) {curNode.right = new Node(val);ans = Math.max(ans, curDepth + 1);return;}dfs(curNode.right, val, curDepth + 1);} else {if (curNode.mid == null) {curNode.mid = new Node(val);ans = Math.max(ans, curDepth + 1);return;}dfs(curNode.mid, val, curDepth + 1);}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] vals = new int[n];for (int i = 0; i < n; i++) {vals[i] = scanner.nextInt();}Node root = new Node(vals[0]);for (int i = 1; i < n; i++) {dfs(root, vals[i], 1);}System.out.println(ans);}
}

cpp

#include <iostream>
#include <vector>using namespace std;struct Node {int val;Node* left;Node* mid;Node* right;Node(int val) : val(val), left(nullptr), mid(nullptr), right(nullptr) {}
};int ans = 1;void dfs(Node* curNode, int val, int curDepth) {if (curNode->val - val < -500) {if (curNode->left == nullptr) {curNode->left = new Node(val);ans = max(ans, curDepth + 1);return;}dfs(curNode->left, val, curDepth + 1);} else if (curNode->val - val > 500) {if (curNode->right == nullptr) {curNode->right = new Node(val);ans = max(ans, curDepth + 1);return;}dfs(curNode->right, val, curDepth + 1);} else {if (curNode->mid == nullptr) {curNode->mid = new Node(val);ans = max(ans, curDepth + 1);return;}dfs(curNode->mid, val, curDepth + 1);}
}int main() {int n;cin >> n;vector<int> vals(n);for (int i = 0; i < n; i++) {cin >> vals[i];}Node* root = new Node(vals[0]);for (int i = 1; i < n; i++) {dfs(root, vals[i], 1);}cout << ans << endl;return 0;
}

解法二：建树完毕后计算树的高度

python

# 题目：【DFS】2023C-计算三叉搜索树的高度
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：DFS/树（解法二：建树完毕后计算树的高度）
# 代码看不懂的地方，请直接在群上提问# 构建树节点类
class Node:def __init__(self, val):self.val = valself.left = Noneself.mid = Noneself.right = None# 创建dfs函数，用于对树插入值为val的节点
# 参数cur_node表示与val进行比较的当前节点
def dfs(cur_node, val):# 插入节点insert_node位于当前节点cur_node左子树的情况if cur_node.val - val < -500:# 若cur_node的左节点不存在，则新建插入节点# insert_node = Node(val)# 并将其插入cur_node的左节点中if cur_node.left is None:cur_node.left = Node(val)return# 否则对左节点进行递归调用，继续比较dfs(cur_node.left, val)# 插入节点insert_node位于当前节点cur_node右子树的情况elif cur_node.val - val > 500:# 若cur_node的右节点不存在，则新建插入节点# insert_node = Node(val)# 并将其插入cur_node的右节点中if cur_node.right is None:cur_node.right = Node(val)return# 否则对右节点进行递归调用，继续比较dfs(cur_node.right, val)# 插入节点insert_node位于当前节点cur_node中间子树的情况else:# 若cur_node的终极那节点不存在，则新建插入节点# insert_node = Node(val)# 并将其插入cur_node的中间节点中if cur_node.mid is None:cur_node.mid = Node(val)return# 否则对中间节点进行递归调用，继续比较dfs(cur_node.mid, val)# 用于计算树高度的递归函数
# node为当前节点，cur_depth为当前高度
def dfs_cal_height(node, cur_depth):if node == None:returnglobal ansans = max(cur_depth, ans)dfs_cal_height(node.left, cur_depth+1)dfs_cal_height(node.mid, cur_depth+1)dfs_cal_height(node.right, cur_depth+1)# 输入节点数目n
n = int(input())
# 输入节点值数组vals
vals = list(map(int, input().split()))
# 构建根节点，根节点的值一定为vals数组中的第一个元素
root = Node(vals[0])# 遍历除了根节点以外的其他节点的值val
# 这个值对应插入节点insert_node
for val in vals[1:]:# 对于每一个节点的值val，都调用dfs函数# 递归入口传入根节点root，插入新的值为val的节点dfs(root, val)ans = 1
# 计算树的高度的函数，递归调用一次即可，传入节点为根节点和起始高度1
dfs_cal_height(root, 1)print(ans)

java

import java.util.Scanner;class Main {static class Node {int val;Node left, mid, right;Node(int val) {this.val = val;}}static int ans = 1;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] vals = new int[n];for (int i = 0; i < n; i++) {vals[i] = scanner.nextInt();}Node root = new Node(vals[0]);for (int i = 1; i < n; i++) {dfs(root, vals[i]);}dfs_cal_height(root, 1);System.out.println(ans);}static void dfs(Node curNode, int val) {if (curNode.val - val < -500) {if (curNode.left == null) {curNode.left = new Node(val);return;}dfs(curNode.left, val);} else if (curNode.val - val > 500) {if (curNode.right == null) {curNode.right = new Node(val);return;}dfs(curNode.right, val);} else {if (curNode.mid == null) {curNode.mid = new Node(val);return;}dfs(curNode.mid, val);}}static void dfs_cal_height(Node node, int curDepth) {if (node == null) {return;}ans = Math.max(curDepth, ans);dfs_cal_height(node.left, curDepth + 1);dfs_cal_height(node.mid, curDepth + 1);dfs_cal_height(node.right, curDepth + 1);}
}

cpp

#include <iostream>
#include <vector>
using namespace std;class Node {
public:int val;Node* left;Node* mid;Node* right;Node(int val) {this->val = val;left = nullptr;mid = nullptr;right = nullptr;}
};int ans = 1;void dfs(Node* curNode, int val) {if (curNode->val - val < -500) {if (curNode->left == nullptr) {curNode->left = new Node(val);return;}dfs(curNode->left, val);} else if (curNode->val - val > 500) {if (curNode->right == nullptr) {curNode->right = new Node(val);return;}dfs(curNode->right, val);} else {if (curNode->mid == nullptr) {curNode->mid = new Node(val);return;}dfs(curNode->mid, val);}
}void dfs_cal_height(Node* node, int curDepth) {if (node == nullptr) {return;}ans = max(curDepth, ans);dfs_cal_height(node->left, curDepth + 1);dfs_cal_height(node->mid, curDepth + 1);dfs_cal_height(node->right, curDepth + 1);
}int main() {int n;cin >> n;vector<int> vals(n);for (int i = 0; i < n; i++) {cin >> vals[i];}Node* root = new Node(vals[0]);for (int i = 1; i < n; i++) {dfs(root, vals[i]);}dfs_cal_height(root, 1);cout << ans << endl;return 0;
}

时空复杂度

时间复杂度：O(NlogN)。建树的时间复杂度。

空间复杂度：O(N)。树所占空间。

华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

  • 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

这篇关于【独家OD2023C卷真题】20天拿下华为OD笔试【DFS】2023C-计算三叉搜索树的高度【欧弟算法】全网注释最详细分类最全的华为OD真题题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/439438。

相关文章

Flutter实现文字镂空效果的详细步骤

Flutter实现文字镂空效果的详细步骤

《Flutter实现文字镂空效果的详细步骤》：本文主要介绍如何使用Flutter实现文字镂空效果,包括创建基础应用结构、实现自定义绘制器、构建UI界面以及实现颜色选择按钮等步骤,并详细解析了混合模... 目录引言实现原理开始实现步骤1：创建基础应用结构步骤2：创建主屏幕步骤3：实现自定义绘制器步骤4：构建U
阅读更多...
IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》：本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1：创建 Maven Web 项目步骤 2：添加 Spring MVC 依赖1、保存后执行2、将新的依赖
阅读更多...
Pandas使用AdaBoost进行分类的实现

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost？使用 AdaBoost 的步骤安装必要的库步骤一：数据准备步骤二：模型
阅读更多...
如何为Yarn配置国内源的详细教程

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方
阅读更多...
最详细安装 PostgreSQL方法及常见问题解决

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》：本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.
阅读更多...
MySql match against工具详细用法

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引（Full-Textindex）的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七
阅读更多...
python中各种常见文件的读写操作与类型转换详细指南

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件（txt,xls,csv,sql,二进制文件）的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1
阅读更多...
Linux内核参数配置与验证详细指南

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数（sysctl）的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置（重启失效）3.2 永久设置（重启仍生效
阅读更多...
IDEA自动生成注释模板的配置教程

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注
阅读更多...
如何在Mac上安装并配置JDK环境变量详细步骤

如何在Mac上安装并配置JDK环境变量详细步骤

《如何在Mac上安装并配置JDK环境变量详细步骤》：本文主要介绍如何在Mac上安装并配置JDK环境变量详细步骤,包括下载JDK、安装JDK、配置环境变量、验证JDK配置以及可选地设置PowerSh... 目录步骤 1：下载JDK步骤 2：安装JDK步骤 3：配置环境变量1. 编辑~/.zshrc（对于zsh
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2