漫画：二叉树系列 第四讲（BST的查找）

在上一节中，我们学习了二叉搜索树。那我们如何在二叉搜索树中查找一个元素呢？和普通的二叉树又有何不同？我们将在本节内容中进行学习！

下面看题：???

01

第700题：二叉搜索树中的搜索

第700题：给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。

例如，给定二叉搜索树:

4

/ \

2 7

/ \

1 3

搜索: 2

你应该返回如下子树:

2

/ \

1 3

在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

本题为必须掌握

需要非常熟悉

为后续题目打基础

02

复习巩固

先复习一下，二叉搜索树（BST）的特性：

1.若它的左子树不为空，则所有左子树上的值均小于其根节点的值

2.若它的右子树不为空，则所有右子树上的值均大于其根节点得值

3.它的左右子树也分别为二叉搜索树

如下图就是一棵典型的BST：

03

图解分析

假设目标值为 val。

根据BST的特性，我们可以很容易想到查找过程

• 如果val小于当前结点的值，转向其左子树继续搜索；
• 如果val大于当前结点的值，转向其右子树继续搜索；
• 如果已找到，则返回当前结点。

很简单，不是吗？

04

代码如下

给出递归和迭代两种解法：

//java

//递归
public TreeNode searchBST(TreeNode root, int val) {
    if (root == null)
        return null;
    if (root.val > val) {
        return searchBST(root.left, val);
    } else if (root.val < val) {
        return searchBST(root.right, val);
    } else {
        return root;
    }
}

//迭代
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 {
            root = root.right;
        }
    }
    return null;
}

递归与迭代的区别

递归：重复调用函数自身实现循环称为递归；

迭代：利用变量的原值推出新值称为迭代，或者说迭代是函数内某段代码实现循环；

04

特别说明

本题确实很简单！专门拉出来讲解的目的有二。第一BST确实很重要，第二希望通过重复，能加深大家对BST的印象，不至于和后面的内容出现交叉感染！

学会了吗？

无论是不理解还是有别的解题思路都可以在评论区进行留言~

如果已完全掌握，一定记得点击右方“在看”进行每日打卡！

还没进群的小伙伴抓紧啦！

注：本系列所有教程中都不会用到复杂的语言特性，大家不需要担心没有学过相关语法。算法思想最重要，使用各语言纯属本人爱好。同时，本系列所有代码均在leetcode上进行过测试运行，保证其严谨性！