树与图简单3 种解法

#700二叉搜索树中的搜索

返回二叉搜索树中值等于目标值的节点及其子树。

#二叉搜索树#深度优先搜索#迭代

解题主线

BST 的有序性让每一步只需选择一个方向。

解法 1：普通树 DFS

先搜索左子树，未找到再搜索右子树，展示不利用 BST 的基线方案。

时间复杂度

O(n)

空间复杂度

O(h)

700. 二叉搜索树中的搜索 · 普通树 DFS

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) return root;
        TreeNode left = searchBST(root.left, val);
        return left != null ? left : searchBST(root.right, val);
    }
}

先搜索左子树，未找到再搜索右子树，展示不利用 BST 的基线方案。

解法 2：BST 递归搜索

目标较小时只搜索左子树，较大时只搜索右子树。

时间复杂度

O(h)

空间复杂度

O(h)

700. 二叉搜索树中的搜索 · BST 递归搜索

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) return root;
        return val < root.val ? searchBST(root.left, val)
                : searchBST(root.right, val);
    }
}

目标较小时只搜索左子树，较大时只搜索右子树。

解法 3：BST 迭代搜索

沿唯一候选路径移动直到命中或为空。

时间复杂度

O(h)

空间复杂度

O(1)

700. 二叉搜索树中的搜索 · BST 迭代搜索

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode current = root;
        while (current != null && current.val != val) {
            current = val < current.val ? current.left : current.right;
        }
        return current;
    }
}

沿唯一候选路径移动直到命中或为空。

边界与易错点

普通二叉树 DFS 虽正确但没有利用 BST，时间和栈空间都可能更高。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q700_searchBST.java