【独家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。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
基于人工智能的图像分类系统

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2