【力扣题解】P700-二叉搜索树中的搜索-Java题解

花无缺

👨‍💻博客主页：@花无缺
欢迎点赞👍 收藏⭐ 留言📝 加关注✅!
本文由 花无缺 原创

收录于专栏【力扣题解】

文章目录

【力扣题解】P700-二叉搜索树中的搜索-Java题解
- 🌏题目描述
- 💡题解
- 🌏总结

【力扣题解】P700-二叉搜索树中的搜索-Java题解

P700. 二叉搜索树中的搜索

🌏题目描述

给定二叉搜索树（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

💡题解

递归：

public TreeNode searchBST(TreeNode root, int val) {
    // 节点为空, 说明没有搜索到 val 值, 返回 null
    if (root == null) {
        return null;
    }
    // val 等于当前节点值, 返回当前节点
    if (root.val == val) {
        return root;
    }
    // 如果 val 比当前节点值小, 就搜索左子树
    if (val < root.val) {
        return searchBST(root.left, val);
    }
    // 如果 val 比当前节点值大, 就搜索右子树
    return searchBST(root.right, val);
}

利用栈迭代：

public TreeNode searchBST(TreeNode root, int val) {
    // 根节点为空, 返回 null
    if (root == null) {
        return null;
    }
    // 根节点值就等于 val, 返回根节点
    if (root.val == val) {
        return root;
    }
    // 使用栈遍历树
    Deque<TreeNode> stack = new LinkedList<>();
    stack.offerLast(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pollLast();
        // 当前节点值等于 val, 直接返回当前节点
        if (node.val == val) {
            return node;
        }
        // 左右子节点进栈
        if (node.left != null) {
            stack.offerLast(node.left);
        }
        if (node.right != null) {
            stack.offerLast(node.right);
        }
    }
    // 搜索完整个二叉搜索树都没有找到 val 值, 返回 null
    return null;
}

利用二叉搜索树的特性迭代：

public TreeNode searchBST(TreeNode root, int val) {
    // 当前节点不为空
    while (root != null) {
        // val 小于当前节点值
        if (root.val > val) {
            // 搜索左子树
            root = root.left;
        //     val 大于当前节点值
        } else if (root.val < val) {
            // 搜索右子树
            root = root.right;
        //     val 等于当前节点值, 直接返回当前节点
        } else {
            return root;
        }
    }
    // 当前节点为空, 说明没有搜索到 val 值, 返回 null
    return null;
}

时间复杂度均为O(n)，需要遍历 n 个二叉搜索树的节点，n <= 二叉搜索树的节点数。

🌏总结

这个题我们可以直接使用递归轻松的做出来，而且也可以使用迭代，但是本题除了使用常规的用栈模拟递归来迭代之外，我们还可以有更加简单的迭代法，那就是利用二叉搜索树的特性，二叉搜索树左子树上所有结点的值均小于它的根结点的值，二叉搜索树右子树上所有结点的值均大于它的根结点的值，而且它的所有子树都是二叉搜索树。根据这个特性，我们就不需要使用栈来迭代，而直接根据当前节点的左右子节点的大小来进行迭代，这样会更加的简单高效。

作者：花无缺(huawuque404.com)