当前位置:网站首页>leetcode刷题:二叉树20(二叉搜索树中的搜索)
leetcode刷题:二叉树20(二叉搜索树中的搜索)
2022-07-07 10:30:00 【涛涛英语学不进去】
700.二叉搜索树中的搜索
给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。
例如,
在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。
很简单的一题。递归,当前结点为空时,返回空,当前结点比目标数大,则查左子树,否则查右子树,若相等,则返回。因为二叉搜索树是中序非递减的。即有序的,二分法思想。
package com.programmercarl.tree;
/** * @ClassName SearchBST * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 21:17 * @Version 1.0 * https://leetcode.cn/problems/search-in-a-binary-search-tree/ * 700. 二叉搜索树中的搜索 **/
public class SearchBST {
/** * BST,又叫平衡二叉树,是一种循关键码访问的二叉树, * 并且要求保持顺序性,即任一节点不小于其左后代,不大于其右后代(注意是后代,不是孩子)。 * BST的顺序性使得其中序遍历序列一定是单调非降的。 * * @param root * @param val * @return */
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
} else if (root.val < val) {
//当前值比目标值小,在右子树上搜
return searchBST(root.right, val);
} else {
//当前值比目标值大,在左子树上搜
return searchBST(root.left, val);
}
}
}
边栏推荐
- Decrypt gd32 MCU product family, how to choose the development board?
- 【统计学习方法】学习笔记——逻辑斯谛回归和最大熵模型
- BGP third experiment report
- EPP+DIS学习之路(1)——Hello world!
- 普乐蛙小型5d电影设备|5d电影动感电影体验馆|VR景区影院设备
- 111. Network security penetration test - [privilege escalation 9] - [windows 2008 R2 kernel overflow privilege escalation]
- TypeScript 接口继承
- wallys/Qualcomm IPQ8072A networking SBC supports dual 10GbE, WiFi 6
- Static comprehensive experiment
- 盘点JS判断空对象的几大方法
猜你喜欢
解密GD32 MCU产品家族,开发板该怎么选?
浅谈估值模型 (二): PE指标II——PE Band
<No. 9> 1805. Number of different integers in the string (simple)
2022 8th "certification Cup" China University risk management and control ability challenge
金融数据获取(三)当爬虫遇上要鼠标滚轮滚动才会刷新数据的网页(保姆级教程)
zero-shot, one-shot和few-shot
wallys/Qualcomm IPQ8072A networking SBC supports dual 10GbE, WiFi 6
File upload vulnerability - upload labs (1~2)
ENSP MPLS layer 3 dedicated line
111. Network security penetration test - [privilege escalation 9] - [windows 2008 R2 kernel overflow privilege escalation]
随机推荐
Up meta - Web3.0 world innovative meta universe financial agreement
TypeScript 接口继承
Decrypt gd32 MCU product family, how to choose the development board?
静态Vxlan 配置
Xiaohongshu microservice framework and governance and other cloud native business architecture evolution cases
idea 2021中文乱码
AirServer自动接收多画面投屏或者跨设备投屏
Tutorial on the principle and application of database system (008) -- exercises on database related concepts
File upload vulnerability - upload labs (1~2)
<No. 9> 1805. 字符串中不同整数的数目 (简单)
Several methods of checking JS to judge empty objects
On valuation model (II): PE index II - PE band
Zhimei creative website exercise
Customize the web service configuration file
Tutorial on principles and applications of database system (009) -- conceptual model and data model
数据库系统原理与应用教程(010)—— 概念模型与数据模型练习题
SQL lab 11~20 summary (subsequent continuous update) contains the solution that Firefox can't catch local packages after 18 levels
Tutorial on principles and applications of database system (010) -- exercises of conceptual model and data model
Is it safe to open an account in Ping An Securities mobile bank?
消息队列消息丢失和消息重复发送的处理策略