LeetCode 0700.二叉搜索树中的搜索

二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点root和一个整数值val。

你需要在BST中找到节点值等于val的节点。返回以该节点为根的子树。如果节点不存在，则返回null。

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

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

确定递归函数的参数和返回值
- 参数：传入根节点和要搜索的值
- 返回值：搜索数值所在节点为根节点的树
确定终止条件
- 终止条件：根节点为空或找到要搜索的值
确定单层递归的逻辑
- 因为二叉搜索树的节点是有序的，所以可以有方向的去搜索
- 若中间节点大于目标值就向左搜索，若小于目标节点就向右搜索，最后如果都没有搜索到，就返回NULL

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


//二叉搜索树中的搜索
func searchBST(root *TreeNode, val int) *TreeNode {
    //若传入节点为空或找到要搜索的值,直接返回该节点
    if root == nil || root.Val == val {
        return root
    }
    //若中间节点大于目标值就向左搜索
    if root.Val > val {
        return searchBST(root.Left, val) //递归
    }
    //若中间节点小于目标节点就向右搜索
    return searchBST(root.Right, val) //递归
}

Link

GitHub