LeetCode 二叉搜索树系列 ～ 二叉搜索树中的搜索

携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第7天，点击查看活动详情

二叉搜索树的定义

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

二叉搜索树主要支持三个操作

搜索

关于二叉搜索树的搜索，对于每个节点：

• 如果目标值等于节点的值，则返回节点；
• 如果目标值小于节点的值，则继续在左子树中搜索；
• 如果目标值大于节点的值，则继续在右子树中搜索。

插入

插入到操作与搜索类似，对于每个节点：

• 根据节点值与目标节点值的关系，搜索左子树或右子树；
• 重复上一步直到到达外部节点；
• 根据节点的值与目标节点的值的关系，将新节点添加为其左侧或右侧的子节点。

删除

删除的操作比起前两个操作会稍微复杂些，需要注意的点如下：

• 如果目标节点没有子节点，我们可以直接移除该目标节点。
• 如果目标节只有一个子节点，我们可以用其子节点作为替换。
• 如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。

题目

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

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

示例

输入： root = [4,2,7,1,3], val = 2
输出： [2,1,3]

输入： root = [4,2,7,1,3], val = 5
输出： []

提示

• 数中节点数在 [1, 5000] 范围内
• 1 <= Node.val <= 10^7
• root 是二叉搜索树
• 1 <= val <= 10^7

二叉搜索树中的搜索代码实现

/** * 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(null == root){
            return root;
        }

        // 匹配到对应节点，放回该节点
        if(root.val == val){
            return root;
        }else if(root.val > val){
            // 如果当前节点值大于目标值，则向左搜索
            return searchBST(root.left, val);
        }else{
            // 如果当前节点值小于目标值，则向右搜索
            return searchBST(root.right, val);
        }
    }
}