LeetCode_二叉搜索树_简单_700.二叉搜索树中的搜索
2023-09-27 14:25:46 时间
1.题目
给定二叉搜索树(BST)的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。
示例 1:
输入:root = [4,2,7,1,3], val = 2
输出:[2,1,3]
示例 2:
输入:root = [4,2,7,1,3], val = 5
输出:[]
提示:
数中节点数在 [1, 5000] 范围内
1 <= Node.val <= 107
root 是二叉搜索树
1 <= val <= 107
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/search-in-a-binary-search-tree
2.思路
(1)递归
3.代码实现(Java)
//思路1————递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) {
return null;
}
if (root.val > val) {
//root.val > val说明该节点可能在左子树中,故搜索左子树
return searchBST(root.left, val);
}
if (root.val < val) {
//root.val < val说明该节点可能在右子树中,故搜索右子树
return searchBST(root.right, val);
}
//root.val = val,即当前根节的值恰好为val,直接返回root即可
return root;
}
}
相关文章
- 【LeetCode】不同的二叉搜索树 [M](卡特兰数)
- 【LeetCode】颜色分类 [M](快速排序)
- 【LeetCode】跳跃游戏 [M](模拟)
- 【LeetCode】恢复二叉搜索树 [M](Morris遍历)
- 【LeetCode】我能赢吗 [M](记忆化搜索)
- LeetCode_BFS_困难_864.获取所有钥匙的最短路径
- LeetCode_滑动窗口_前缀和_二分搜索_中等_209.长度最小的子数组
- LeetCode_二分搜索_简单_69. x 的平方根
- LeetCode_映射_简单_645.错误的集合
- LeetCode_二叉搜索树_中等_96.不同的二叉搜索树
- LeetCode_二叉树_中等_116.填充每个节点的下一个右侧节点指针
- LeetCode_二分搜索_中等_1011.在 D 天内送达包裹的能力
- LeetCode_二分搜索_阶乘_困难_793.阶乘函数后 K 个零
- LeetCode_二分搜索_简单_704.二分查找
- LeetCode_二分搜索_简单_35.搜索插入位置
- LeetCode_二分搜索_中等_34.在排序数组中查找元素的第一个和最后一个位置
- LeetCode刷题(11)【简单】回文数&罗马数字转整数(C++)
- LeetCode·每日一题·1041. 困于环中的机器人·模拟
- LeetCode·139.单词拆分·递归·记忆化搜索·字典树
- LeetCode·669.修剪二叉搜索树·递归
- [LeetCode]Implement Stack using Queues
- LeetCode-35. 搜索插入位置(Golang实现)
- [LeetCode] 853. Car Fleet 车队
- [LeetCode] 270. Closest Binary Search Tree Value 最近的二叉搜索树的值
- leetcode 96不同的二叉搜索树