树与图简单3 种解法

#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 <= 10⁷
root 是二叉搜索树
1 <= val <= 10⁷

查看原题

解题主线

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

解法 1：普通树 DFS

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

时间复杂度： O(n)
空间复杂度： O(h)

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;
        // 普通 DFS 不利用 BST 性质，先完整搜索左子树
        TreeNode left = searchBST(root.left, val);
        // 左侧未命中时才继续搜索右子树
        return left != null ? left : searchBST(root.right, val);
    }
}

解法 2：BST 递归搜索

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

时间复杂度： O(h)
空间复杂度： O(h)

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;
        // BST 有序性保证目标只可能位于一个方向，可直接剪掉另一子树
        return val < root.val ? searchBST(root.left, val)
                : searchBST(root.right, val);
    }
}

解法 3：BST 迭代搜索

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

时间复杂度： O(h)
空间复杂度： O(1)

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;
        // current 始终指向唯一仍可能包含目标值的候选路径
        while (current != null && current.val != val) {
            // 根据 BST 有序性选择一侧，另一整棵子树可直接排除
            current = val < current.val ? current.left : current.right;
        }
        // 命中时返回目标子树，路径耗尽时返回 null
        return current;
    }
}

边界与易错点

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

整理来源

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

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