首页 > 编程语言 >【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【DFS】2024D-计算三叉搜索树的高度【欧弟算法】全网注释最详细分类最全的华为OD真题题解

【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【DFS】2024D-计算三叉搜索树的高度【欧弟算法】全网注释最详细分类最全的华为OD真题题解

时间：2024-06-14 17:57:11浏览次数：13  
标签：node Node cur val 真题 OD dfs 节点 2024D

有LeetCode算法/华为OD考试扣扣交流群可加 948025485
可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

文章目录

从2024年4月15号开始，OD机考全部配置为2024D卷。
注意两个关键点：

  1. 会遇到C卷复用题。虽然可能存在幸存者偏差，但肯定还会有一大部分的旧题。
  2. 现在又支持做完题目之后倒回去改了。就是可以先做200的再做100的，然后可以反复提交。

在这里插入图片描述

题目描述与示例

题目描述：

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

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

查找的规则是：

  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 = val
        self.left = None
        self.mid  = None
        self.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)
            return
        dfs(cur_node.left, val)
    elif cur_node.val - val > 500:
        if cur_node.right is None:
            cur_node.right = Node(val)
            return
        dfs(cur_node.right, val)
    else:
        if cur_node.mid is None:
            cur_node.mid = Node(val)
            return
        dfs(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 ans
    if cur_node.val - val < -500:
        if cur_node.left is None:
            cur_node.left = Node(val)
            ans = max(ans, cur_depth + 1)
            return
        dfs(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)
            return
        dfs(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)
            return
        dfs(cur_node.mid, val, cur_depth + 1)

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

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

def dfs_cal_height(node, cur_depth):
    if node == None:
        return
    global ans
    ans = 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 = val
        self.left = None
        self.mid = None
        self.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
        # 否则对左节点进行递归调用，继续比较，同时深度+1
        dfs(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
        # 否则对右节点进行递归调用，继续比较，同时深度+1
        dfs(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
        # 否则对中间节点进行递归调用，继续比较，同时深度+1
        dfs(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的节点
    # 当前深度为1
    dfs(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 = val
        self.left = None
        self.mid = None
        self.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:
        return
    global ans
    ans = 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算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务300+同学成功上岸！

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

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

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

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

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

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

标签：node,Node,cur,val,真题,OD,dfs,节点,2024D
From： https://blog.csdn.net/weixin_48157259/article/details/139639972

相关文章

  • 核心（Hutool-core）工具类(社会信用代码工具-CreditCodeUtil)
    介绍法人和其他组织统一社会信用代码制度，相当于让法人和其他组织拥有了一个全国统一的“身份证号”。规则如下：第一部分：登记管理部门代码1位(数字或大写英文字母)第二部分：机构类别代码1位(数字或大写英文字母)第三部分：登记管理机关行政区划码6位(数字)第四部分：主体标识码（......
  • vscode报错
    参考——https://www.cnblogs.com/greystone/p/14062510.htmlhttps://www.cnblogs.com/WMT-Azura/p/11137972.html 具体报错: .:无法加载文件...\WindowsPowerShell\profile.ps1，因为在此系统上禁止运行脚本。有关详细信息，请参阅https:/go.microsoft.com/fwlin......
  • node 相关
     查看当前NPM仓库地址npmconfiggetregistry这个命令会返回当前配置的NPM仓库URL，通常默认是 https://registry.npmjs.org/。切换到官方NPM仓库npmconfigsetregistryhttps://registry.npmjs.org/切换到淘宝NPM镜像淘宝NPM镜像是一个流行的选项，尤其是对于位于中国大......
  • element-plus el-table spanMethod 行合并通用方法 可实现数据的自动整理
    importtype{TableColumnCtx}from'element-plus'interfaceSpanMethodProps<T>{row:T&Record<string,any>column:TableColumnCtx<T>rowIndex:numbercolumnIndex:number}/***el-table行合并方法*@par......
  • 华为OD API集群负载统计
    题目描述：某个产品的RESTfulAPI集合部署在服务器集群的多个节点上，近期对客户端访问日志进行了采集，需要统计各个API的访问频次，根据热点信息在服务器节点之间做负载均衡，现在需要实现热点信息统计查询功能。RESTfulAPI的由多个层级构成，层级之间使用/连接，如/A/B/C/D这个地址......
  • LeetCode刷题之HOT100之二叉树的遍历
    2024/6/14这几天总是下雨，天气预报上面显示这个月都要持续下雨，下雨天了怎么办？我好想你，不敢打给你，我找不到原因。说着说着唱起来了哈哈！Anyway，昨天晚上打开了《涅朵奇卡一个女人的一生》，这本篇幅不长的小说我很久前就想看，还是从王小波那里知道的这本书，才开始看陀思妥耶夫斯基，......
  • 代码随想录 算法训练营 day9 Leetcode151 反转字符串单词 karma55 右旋转字符串 28 实
    Leetcode151反转字符串单词题目链接讲解此题方法很多很重要注重基础解法classSolution{publicStringreverseWords(Strings){char[]initialArr=s.toCharArray();//新字符数组char[]newArr=newchar[initialArr.length+1];//下......
  • ESP8266 NodeMCU Lua 开发看这里
    最近开发ESP8266-NodeMCU因为开发过合宙4G模块，用的Lua，所以这里也用Lua。但是最开始两眼一抹黑，在网上找资料，乱七八糟，需要Lua固件库、LuaAPI文档、Lua例程、固件下载工具、IDE(Lua代码编写和下载)、串口驱动(这是常识，就不用说了)找来找去，气死我了！！！！都是介绍下工具咋使用、弄个d......
  • MongoDB分片（windows电脑系统）
    系统版本：windows10专业版MongoDB:4.4.24分片架构从图中可以看出，分片集群中主要由三个部分组成，即分片服务器（Shard）、路由服务器（Mongos）以及配置服务器（ConfigServer）组成。其中，分片服务器有三个，即Shard1、Shard2、Shard3；路由服务器有两个，即Mongos1和Mongos2；配......
  • MongoDB基本操作（Windows）
    本篇博文介绍知识目标熟悉数据库和集合操作本篇目标掌握MongoDB的部署掌握文档的插入、更新、删除以及查询操作一、MongoDB的安装部署在浏览器输入网址：www.mongodb.com  2. 点击“TRYFREE”或“GETSTARTED”按钮，进入MongoDB的下载页面；3. 在下载页面中，选择适......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99