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

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

1、题目

题目链接：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 <= 107
• root 是二叉搜索树
• 1 <= val <= 107

2、递归

思路

二叉搜索树是一个有序树，满足以下性质：

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

据此可以得到如下算法：
若 root 为空则返回空节点；
若 val = root.val，则返回 root；
若 val < root.val，递归左子树；
若 val > root.val，递归右子树。

1. 确定递归函数的参数和返回值

递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。
代码如下：

TreeNode* searchBST(TreeNode* root, int val)

2. 确定终止条件

如果root为空，或者找到这个数值了，就返回root节点。

if (root == nullptr || root->val == val) {
    return root;
}

3. 确定单层递归的逻辑

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

TreeNode* result = nullptr;
if (root->val > val) result = searchBST(root->left, val);
if (root->val < val) result = searchBST(root->right, val);
return result;

代码

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr || root->val == val) {
            return root;
        }
        // 如果根节点的值大于目标值，则在左子树中继续搜索
        if (root->val > val) {
            return searchBST(root->left, val);
        } else {
            // 如果根节点的值小于目标值，则在右子树中继续搜索
            return searchBST(root->right, val);
        }
    }
};

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)

3、迭代法

思路

我们将方法一的递归改成迭代写法：
若 root 为空则跳出循环，并返回空节点；
若 val=root.val，则返回 root；
若 val<root.val，将 root 置为 root.left；
若 val>root.val，将 root 置为 root.right。

代码

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != nullptr) {
            if (root->val > val) {
                root = root->left;
            } else if (root->val < val) {
                root = root->right;
            } else {
                return root;
            }
        }
        return nullptr;
    }
};

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(1)