题目链接:https://leetcode.cn/problems/search-in-a-binary-search-tree/description/
题目叙述:
给定二叉搜索树(BST)的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。
示例 1:
输入:root = [1,null,2,2]
输出:[2]
示例 2:
输入:root = [0]
输出:[0]
提示:
树中节点的数目在范围 [1, 10^4] 内
-10^5 <= Node.val <= 10^5
思路:
我们首先要知道二叉搜索树是一颗什么树:
二叉搜索树是一个有序树:
若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
它的左、右子树也分别为二叉搜索树
在了解完二叉搜索树以后,我们就可以开始分析了。
这题是查找一个二叉树中的某一个节点的值等于val,本质上就是在二叉树中查找一个节点,它的值为val(不一定存在),那么我们是肯定要遍历这个二叉树的所有节点,又因为这个二叉树不是
普通的二叉树,是二叉搜索树,是有顺序的二叉树,因此我们直接可以根据这个规律来进行搜索,这题我们可以使用递归法和迭代法两种规则
递归法
递归法我们在前面的文章里面也介绍过了,要注意三步:
- 递归函数的参数和返回值:本题我们是查找一个节点的值为val,那么返回值就是TreeNode*,树的结点类型,并且我们要传入一个树的根结点,这就是函数的参数和返回值
- 递归结束的条件:当我们的递归搜索到了空结点或者搜索到的这个结点的值就等于val的时候,我们是不是就应该返回了。所以递归结束的条件是
if(root==NULL||root->val==val) return root;
- 单层递归的逻辑:这题我们单层递归的逻辑很简单,因为二叉搜索树是一颗有序的树,那么我们就直接比对当前结点的值与val的大小,如果
root->val<val
那么我们应该到二叉树的右子树
去搜索;否则就去二叉树的左子树进行搜索。
得出代码:
//递归法在二叉搜索树中搜索值
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL || root->val == val) return root;
TreeNode* result = NULL;
//如果当前结点的值大于val,就搜索左边的树
if (root->val > val) result = searchBST(root->left, val);
//否则,搜索右边的树
if (root->val < val) result = searchBST(root->right, val);
return result;
}
};
迭代法
迭代法也是可以的,和递归的逻辑差不多,当前结点的值大于val,就到左子树去搜索,否则去右子树搜索
迭代法代码:
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while(root!=NULL){
if(root->val==val) return root;
else if(root->val>val) root=root->left;
else if(root->val<val) root=root->right;
}
//没搜到就返回空
return NULL;
}
};
标签:结点,LeetCode700,val,root,二叉,搜索,二叉树,树中
From: https://www.cnblogs.com/Tomorrowland/p/18328828