华为od机试真题 python 实现【查找二叉树节点】

时间: 2023-05-08 11:00:36 浏览: 79
题目描述: 输入一个二叉查找树和一个目标节点值,输出这个目标节点在二叉查找树中的层数。如果这个节点不在树中,输出-1。 算法思路: 二叉查找树能快速找到目标节点,因为左边节点小于右边节点,可以用二分思想来优化查找速度。通过递归,比较当前节点值和目标节点值的大小,若相等则返回当前层数即可,若目标节点值小于当前节点值,则向左子树递归查找,否则向右子树递归查找。如果找到节点则返回当前层数,如果递归到叶子节点仍未找到,返回-1。 代码实现: class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def searchBST(self, root: TreeNode, val: int) -> int: if root.val == val: return 1 elif val < root.val and root.left: return self.searchBST(root.left, val) + 1 elif val > root.val and root.right: return self.searchBST(root.right, val) + 1 else: return -1 测试样例: root = TreeNode(4) root.left = TreeNode(2) root.right = TreeNode(7) root.left.left = TreeNode(1) root.left.right = TreeNode(3) s = Solution() print(s.searchBST(root, 2)) # 2 print(s.searchBST(root, 5)) # -1 代码解释: 首先定义了一个节点类,包含节点值、左子树和右子树。然后是主要代码部分,将树的根节点和目标节点值作为参数传入函数中。如果当前节点值等于目标节点,则返回当前层数1。如果目标节点值小于当前节点值,且左子树存在,则将目标节点值和左子节点作为参数递归调用函数,返回值加1。如果目标节点值大于当前节点值,且右子树存在,则将目标节点值和右子节点作为参数递归调用函数,返回值加1。如果目标节点不在树中,返回-1。最后的测试样例中,对于二叉树的根节点的左子树中的值为2的节点,输出的结果是2;对于不存在于二叉树中的节点值为5的节点,输出的结果是-1。

相关推荐

### 回答1: 华为OD 2023B卷是华为公司的一份机试试卷,主要考察Java编程能力。以下是我对这个题目的回答。 华为OD 2023B卷的试题主要围绕Java编程的相关知识展开。具体的试题可能包括但不限于以下几个方面: 1. Java基础知识:试题会涉及Java语言的基本语法、关键字、数据类型、运算符等方面的问题,考察对Java基础知识的理解和熟练运用能力。 2. 面向对象编程:试题可能涉及到面向对象的相关概念,例如类、对象、封装、继承、多态等,考察对面向对象思想的掌握程度。 3. 数据结构与算法:试题会涉及到常用的数据结构和算法,例如数组、链表、栈、队列、二叉树、排序算法等,考察对数据结构和算法的理解和能够用Java实现的能力。 4. 异常处理:试题可能会涉及到Java中异常处理的相关知识,例如异常的分类、异常处理机制、try-catch-finally语句等,考察对异常处理的理解和熟练运用能力。 5. 多线程编程:试题可能会涉及到Java多线程编程的相关知识,例如线程的创建与启动、线程同步与通信、线程池等,考察对多线程编程的理解和熟练运用能力。 总的来说,华为OD 2023B卷的试题是比较全面的,涉及到了Java编程的各个方面,旨在考察考生对Java语言的理解和熟练运用能力。考生需要通过阅读题目、分析问题、灵活运用所学知识进行解答,展现自己的编程实力。 ### 回答2: 华为OD机试真题2023B卷中,Java部分包含了以下几个问题: 1. 题目:请编写一个Java程序,计算并输出1到100的所有奇数之和。 解答: java public class OddSum { public static void main(String[] args) { int sum = 0; for (int i = 1; i <= 100; i += 2) { sum += i; } System.out.println("1到100的所有奇数之和为:" + sum); } } 2. 题目:请编写一个Java程序,将一个字符串反转输出。 解答: java public class ReverseString { public static void main(String[] args) { String str = "Hello World"; StringBuilder sb = new StringBuilder(str); System.out.println(sb.reverse().toString()); } } 3. 题目:请编写一个Java程序,实现冒泡排序算法对一个整型数组进行升序排序。 解答: java public class BubbleSort { public static void main(String[] args) { int[] arr = {5, 2, 9, 3, 1}; for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } for (int num : arr) { System.out.print(num + " "); } } } 以上是对华为OD机试真题2023B卷中Java部分题目的回答。其中分别包含了计算奇数之和、字符串反转输出和冒泡排序的实现。
Java华为机试必备函数主要包括以下几个方面: 1. 输入输出函数:在机试中通常需要从标准输入读取数据,并将计算结果输出到标准输出。常用的输入输出函数包括Scanner类的next()、nextInt()等方法用于读取数据,以及System.out.println()等方法用于输出计算结果。 2. 字符串操作函数:字符串操作是机试中常见的任务之一,比如字符串的拼接、截取、查找等。Java中提供了许多字符串操作函数,如String类的concat()、substring()、indexOf()等方法,可以满足处理字符串的需求。 3. 数组操作函数:机试中经常需要对数组进行操作,包括数组的排序、查找、筛选等。Java中提供了Arrays类,其中包含了许多方便的数组操作函数,如sort()、binarySearch()、copyOf()等方法,可以简化对数组的处理过程。 4. 数据结构函数:机试中常用的数据结构包括栈、队列、链表、二叉树等,对于这些数据结构的操作往往需要使用相应的函数。Java中提供了许多数据结构相关的类和接口,如Stack类、Queue接口、LinkedList类、TreeNode类等,可以方便地进行数据结构的操作。 5. 数学函数:机试中会涉及到一些数学计算,比如取模、求平方根、求最大公约数等。Java中提供了Math类,其中包含了许多数学计算相关的函数,如abs()、sqrt()、gcd()等方法,可以进行常见的数学计算。 除了上述函数外,还需要熟悉Java的基本语法和面向对象的思想,以及常见的算法和数据结构,这样才能在华为机试中取得较好的成绩。
在牛客 a卷2022年第四季度的华为题目中,要求考生设计一种高效的数据结构,能够支持以下几种操作: 1. 添加一个元素 2. 删除一个元素 3. 查找是否存在某个元素 4. 返回元素的总数 该数据结构要求满足空间复杂度较小、时间复杂度较低、能够快速地进行查找和修改等多种操作。 想要编写这样一种数据结构,我们可以参考许多已有的经典算法与数据结构,如二叉树、哈希表、红黑树等,通过综合利用它们的优点来实现这个问题的解决。 例如,我们可以通过哈希表来存储所有元素的值,并在每个哈希链表的元素中再使用红黑树来进行排序与查找。这样,我们既能够轻松地进行元素的添加和删除操作,也能够在查找较大数据范围和数量时保持较高的速度与效率。同时,由于使用了多个数据结构来协同完成这个问题,我们也能够在空间复杂度上适度地进行优化。 当然,在具体设计这个数据结构的过程中,我们还需要考虑一些实践中的细节问题,例如如何避免哈希冲突、如何处理数据丢失与被删除元素所占用的空间等问题,这都需要相应的算法与流程来进行处理。 总体来看,设计这种支持多种操作的高效数据结构,需要我们具备丰富的算法知识和编程实践能力,同时需要我们在具体处理问题时能够将多种算法和数据结构进行有效地结合。

最新推荐

300551古鳌科技财务报告资产负债利润现金流量表企业治理结构股票交易研发创新等1391个指标(2013-2022).xlsx

包含1391个指标,其说明文档参考: https://blog.csdn.net/yushibing717/article/details/136115027 数据来源:基于上市公司公告数据整理 数据期间:从具体上市公司上市那一年开始-2022年度的数据,年度数据 包含各上市公司股票的、多年度的上市公司财务报表资产负债表、上市公司财务报表利润表、上市公司财务报表现金流量表间接法、直接法四表合在一个面板里面,方便比较和分析利用 含各个上市公司股票的、多年度的 偿债能力 披露财务指标 比率结构 经营能力 盈利能力 现金流量分析 风险水平 发展能力 每股指标 相对价值指标 股利分配 11类财务指标分析数据合在一个面板里面,方便比较和分析利用 含上市公司公告的公司治理、股权结构、审计、诉讼等数据 包含1391个指标,如: 股票简称 证券ID 注册具体地址 公司办公地址 办公地址邮政编码 董事会秘书 董秘联系电话 董秘传真 董秘电子邮箱 ..... 货币资金 其中:客户资金存款 结算备付金 其中:客户备付金 .........

300472新元科技财务报告资产负债利润现金流量表企业治理结构股票交易研发创新等1391个指标(2012-2022).xlsx

包含1391个指标,其说明文档参考: https://blog.csdn.net/yushibing717/article/details/136115027 数据来源:基于上市公司公告数据整理 数据期间:从具体上市公司上市那一年开始-2022年度的数据,年度数据 包含各上市公司股票的、多年度的上市公司财务报表资产负债表、上市公司财务报表利润表、上市公司财务报表现金流量表间接法、直接法四表合在一个面板里面,方便比较和分析利用 含各个上市公司股票的、多年度的 偿债能力 披露财务指标 比率结构 经营能力 盈利能力 现金流量分析 风险水平 发展能力 每股指标 相对价值指标 股利分配 11类财务指标分析数据合在一个面板里面,方便比较和分析利用 含上市公司公告的公司治理、股权结构、审计、诉讼等数据 包含1391个指标,如: 股票简称 证券ID 注册具体地址 公司办公地址 办公地址邮政编码 董事会秘书 董秘联系电话 董秘传真 董秘电子邮箱 ..... 货币资金 其中:客户资金存款 结算备付金 其中:客户备付金 .........

python统计分析-逻辑回归

python统计分析-逻辑回归

Web新闻管理系统的设计与实现

Web新闻管理系统的设计与实现

天津科技面板数据2021-2000R&D人员经费内外部支出专利申请新产品开发销售出口等429个指标.xlsx

数据范围:本省的科技tj指标 数据年度:2000-2021,22个年度的数据,429个统计指标数据 本数据包含的429个统计指标详见: https://blog.csdn.net/yushibing717/article/details/136286845 综合-研究与试验发展人员_人 综合-研究与试验发展人员-女性研究与试验发展人员_人 综合-研究与试验发展人员-全时人员_人 综合-研究与试验发展人员-博士毕业_人 综合-研究与试验发展人员-硕士毕业_人 综合-研究与试验发展人员-本科毕业_人 综合-研究与试验发展人员全时当量_人年 综合-研究与试验发展人员全时当量-研究人员_人年 综合-研究与试验发展人员全时当量-基础研究_人年 综合-研究与试验发展人员全时当量-应用研究_人年 综合-研究与试验发展人员全时当量-试验发展_人年 综合-研究与试验发展经费内部支出_万元 综合-研究与试验发展经费内部支出-按活动类型-基础研究_万元 综合-研究与试验发展经费内部支出-按活动类型-应用研究_万元 ......

ssm数据结构课程网络学习平台的+vue毕业论文.doc

ssm数据结构课程网络学习平台的+vue毕业论文.doc

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire

Objective-C中的协议与代理设计模式介绍

# 1. 理解Objective-C中的协议 协议是Objective-C中一种很重要的特性,它类似于其他编程语言中的接口,用来定义对象之间的通信规则和行为约定。在Objective-C中,协议可以帮助实现对象之间的松耦合和重用性。让我们深入了解Objective-C中的协议。 ## 1.1 什么是Objective-C中的协议? 在Objective-C中,协议是一组方法的声明,定义了一个对象可以遵循的接口。协议本身并不实现任何方法,而是规定遵循该协议的类需要实现协议中定义的方法。通过协议,可以在不同的类之间定义一组公共的行为和方法。 ## 1.2 协议的声明和使用方法 在Ob

编写求n!的函数f(int n),在主函数中输入两个整数m、n,然后调用函数求: C=m!/n!(m -n)!

好的,我可以编写这个函数。以下是代码示例: ```c++ #include <iostream> using namespace std; int f(int n) { if (n <= 1) { return 1; } else { return n * f(n - 1); } } int main() { int m, n; cout << "请输入两个整数m和n,以空格分隔:" << endl; cin >> m >> n; int C = f(m) / (f(n) * f(m - n));

视频中运动目标跟踪算法的研究.doc

视频中运动目标跟踪算法的研究.doc