当前位置:网站首页>Leetcode skimming: binary tree 20 (search in binary search tree)
Leetcode skimming: binary tree 20 (search in binary search tree)
2022-07-07 12:47:00 【Taotao can't learn English】
700. Search in binary search tree
Given a binary search tree (BST) And a value . You need to BST Found a node whose value is equal to the given value . Return the subtree with this node as the root . If the node doesn't exist , Then return to NULL.
for example ,
In the example above , If the value is 5, But because no node has a value of 5, We should go back to NULL.
A very simple question . recursive , When the current node is empty , Returns an empty , The current node is larger than the target number , Check the left subtree , Otherwise, check the right subtree , If equal , Then return to . Because binary search tree is non decreasing . Orderly , The idea of dichotomy .
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. Search in binary search tree **/
public class SearchBST {
/** * BST, Also called balanced binary tree , It is a binary tree accessed by key , * And it is required to keep the order , That is, any node is not less than its left offspring , Not greater than its right offspring ( Note that offspring , It's not a child ). * BST The order of the ergodic sequence must be monotonic and non descending . * * @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) {
// The current value is smaller than the target value , Search on the right subtree
return searchBST(root.right, val);
} else {
// The current value is larger than the target value , Search on the left sub tree
return searchBST(root.left, val);
}
}
}
边栏推荐
- Static routing assignment of network reachable and telent connections
- AirServer自动接收多画面投屏或者跨设备投屏
- Master formula. (used to calculate the time complexity of recursion.)
- [play RT thread] RT thread Studio - key control motor forward and reverse rotation, buzzer
- 【从 0 开始学微服务】【03】初探微服务架构
- [疑难杂症]pip运行突然出现ModuleNotFoundError: No module named ‘pip‘
- 【二叉树】删点成林
- [statistical learning method] learning notes - support vector machine (I)
- About IPSec
- 【PyTorch实战】图像描述——让神经网络看图讲故事
猜你喜欢
【PyTorch实战】用RNN写诗
Dialogue with Wang Wenyu, co-founder of ppio: integrate edge computing resources and explore more audio and video service scenarios
[statistical learning methods] learning notes - improvement methods
Configure an encrypted web server
File upload vulnerability - upload labs (1~2)
【PyTorch实战】图像描述——让神经网络看图讲故事
[crawler] avoid script detection when using selenium
2022 examination questions and online simulation examination for safety production management personnel of hazardous chemical production units
[statistical learning method] learning notes - logistic regression and maximum entropy model
How to apply @transactional transaction annotation to perfection?
随机推荐
The hoisting of the upper cylinder of the steel containment of the world's first reactor "linglong-1" reactor building was successful
[pytorch practice] use pytorch to realize image style migration based on neural network
Sorting, dichotomy
Day-17 connection set
【从 0 开始学微服务】【02】从单体应用走向服务化
什么是ESP/MSR 分区,如何建立ESP/MSR 分区
About IPSec
Preorder, inorder and postorder traversal of binary tree
[pytorch practice] image description -- let neural network read pictures and tell stories
Using stack to convert binary to decimal
Master公式。(用于计算递归的时间复杂度。)
【PyTorch实战】图像描述——让神经网络看图讲故事
Customize the web service configuration file
ICLR 2022 | pre training language model based on anti self attention mechanism
Creation and assignment of graphic objects
【统计学习方法】学习笔记——第四章:朴素贝叶斯法
SQL lab 26~31 summary (subsequent continuous update) (including parameter pollution explanation)
File upload vulnerability - upload labs (1~2)
gcc 编译报错
利用棧來實現二進制轉化為十進制