700. 二叉搜索树中的搜索
题目描述
输入一棵二叉搜索树的根节点 root（用层序数组表示）和一个整数 val。
在树中找到值等于 val 的节点，返回以它为根的整棵子树，输出同样用层序数组表示。
如果树中没有这个值，返回空（null）。
示例 1
输入：root = [4,2,7,1,3], val = 2 输出：[2,1,3]
解释：值为 2 的节点带着孩子 1 和 3。
示例 2
输入：root = [4,2,7,1,3], val = 5 输出：[]
解释：树中没有值为 5 的节点。
数据范围
- 节点数在
[1, 5000]范围内。 1 <= Node.val <= 10^7root是二叉搜索树。1 <= val <= 10^7
解题思路：迭代查找
BST 的性质：左子树所有值都比根小，右子树所有值都比根大。从根出发，每次比较 val 和当前节点：相等就找到了；val 更小只可能在左子树，往左走；更大就往右走。走到空节点说明不存在。不需要递归，一个指针一路往下即可。
为什么正确
如果 val 在树中，它一定在以当前 node 为根的子树里；每一步都丢掉另一侧整棵子树。
复杂度分析
时间 O(h)，h 是树高，平衡时约 log n，退化成链时为 n；空间 O(1)。
易错点
返回的是整棵子树（节点本身），不是单个值；找不到时返回 null（空树 []）。不要遍历整棵树——那样是 O(n)，没用上 BST 的有序性。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
node = root
while node and node.val != val:
node = node.left if val < node.val else node.right
return nodeclass Solution {
public TreeNode searchBST(TreeNode root, int val) {
TreeNode node = root;
while (node != null && node.val != val)
node = val < node.val ? node.left : node.right;
return node;
}
}class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
TreeNode* node = root;
while (node && node->val != val)
node = val < node->val ? node->left : node->right;
return node;
}
};func searchBST(root *TreeNode, val int) *TreeNode {
node := root
for node != nil && node.Val != val {
if val < node.Val {
node = node.Left
} else {
node = node.Right
}
}
return node
}var searchBST = function(root, val) {
let node = root;
while (node && node.val !== val)
node = val < node.val ? node.left : node.right;
return node;
};function searchBST(root: TreeNode | null, val: number): TreeNode | null {
let node: TreeNode | null = root;
while (node && node.val !== val)
node = val < node.val ? node.left : node.right;
return node;
};其他解法
两种解法的查找路径完全相同；递归版更贴近定义，迭代版把尾递归改成循环，省掉递归栈。
解法 2：递归查找 时间 O(h)，空间 O(h)
节点为空或节点值等于 val 时直接返回该节点。否则 val 较小就递归到左子树，较大就递归到右子树。
写法与二叉搜索树的递归定义一一对应。代价是递归栈占 O(h) 空间，树退化成链时 h = n。
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root or root.val == val:
return root
if val < root.val:
return self.searchBST(root.left, val)
return self.searchBST(root.right, 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);
}
}class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (!root || root->val == val) return root;
return val < root->val ? searchBST(root->left, val) : searchBST(root->right, val);
}
};func searchBST(root *TreeNode, val int) *TreeNode {
if root == nil || root.Val == val {
return root
}
if val < root.Val {
return searchBST(root.Left, val)
}
return searchBST(root.Right, val)
}var searchBST = function(root, val) {
if (!root || root.val === val) return root;
return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
};function searchBST(root: TreeNode | null, val: number): TreeNode | null {
if (!root || root.val === val) return root;
return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}