当前位置：首页 > news >正文

700. 二叉搜索树中的搜索

news 来源：原创 2024/9/28 22:35:09

文章目录

700. 二叉搜索树中的搜索
思路
- 递归法
- 迭代法
总结

700. 二叉搜索树中的搜索

给定二叉搜索树（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 <= 10^7
root 是二叉搜索树
1 <= val <= 10^7

思路

之前我们讲的都是普通二叉树，那么接下来看看二叉搜索树。

二叉搜索树是一个有序树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树

这就决定了，二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样。

本题，其实就是在二叉搜索树中搜索一个节点。那么我们来看看应该如何遍历。

递归法

确定递归函数的参数和返回值
递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。和题目所给一致，故不用新定义辅助函数。

代码如下：

func searchBST(root *TreeNode, val int) *TreeNode {}

确定终止条件
如果root为空，或者找到这个数值了，就返回root节点。

if root == nil || root.Val == val {return root
}

确定单层递归的逻辑
看看二叉搜索树的单层递归逻辑有何不同。因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。如果val < root.Val，搜索左子树，如果val > root.Val，就搜索右子树，最后如果都没有搜索到，就返回nil。

代码如下：

if val < root.Val {return searchBST(root.Left,val)
}
if val > root.Val {return searchBST(root.Right,val)
}
return nil

很多同学写递归函数的时候习惯直接写 searchBST(root.Left, val)，却忘了 递归函数还有返回值。

递归函数的返回值是什么? 是 左子树如果搜索到了val，要将该节点返回。如果不用一个变量将其接住，那么返回值不就没了。

所以要 res = searchBST(root.Left, val)。

整体Go代码如下：

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func searchBST(root *TreeNode, val int) *TreeNode {// 因为是二叉搜索树，所以可以类似二分法一样查找if root == nil || root.Val == val {return root}var res *TreeNodeif val < root.Val {res =  searchBST(root.Left,val)}if val > root.Val {res =  searchBST(root.Right,val)}return res
}

或者我们也可以这么写

此处返回值的深入理解：比如要找的是下图中值为3的节点，则找到之后，在
if root ==nil || root.Val == val {return root }的位置，返回了值为3的节点到上层递归栈，上层递归栈则继续在
if val < root.Val {return searchBST(root.Left,val)}
或
if val > root.Val {return searchBST(root.Right,val)}
处向再上一层递归栈返回值为3的节点，一直这样往上回归，每一层都是返回由下层返回回来的找到那个值为3的节点，直到返回到最开始的那层递归栈的递归入口处，最终得到的结果就是由递归找到结果的某层那一层得到的值为3的节点。

在这里插入图片描述

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func searchBST(root *TreeNode, val int) *TreeNode {// 因为是二叉搜索树，所以可以类似二分法一样查找if root == nil || root.Val == val {return root}if val < root.Val {return searchBST(root.Left,val)}if val > root.Val {return searchBST(root.Right,val)}return nil
}

在这里插入图片描述

迭代法

一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。

对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。

对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。

而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。

例如要搜索元素为3的节点，我们不需要搜索其他节点，也不需要做回溯，查找的路径已经规划好了。

中间节点如果大于3就向左走，如果小于3就向右走，如图：

在这里插入图片描述

所以迭代法代码如下：

//迭代法
func searchBST(root *TreeNode, val int) *TreeNode {for root != nil {if root.Val > val {root = root.Left} else if root.Val < val {root = root.Right} else {return root}}return nil
}