700-二叉搜索树中的搜索

题目地址(700. 二叉搜索树中的搜索 - 力扣（LeetCode）)

https://leetcode.cn/problems/search-in-a-binary-search-tree/submissions/550317560/

题目描述

给定二叉搜索树（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 7
• root   是二叉搜索树
• 1 <= val <= 10 7

思路：中序遍历

对于一棵二叉搜索树来说，中序遍历的结果是一个单调递增的数组。

递归函数定义：

1. 返回值是树的节点，参数是树 root 和目标值 target

public TreeNode searchBST(TreeNode root, int val);

2. 递归终止条件：如果树为空，直接返回 null，如果搜索到叶子节点还没找到，也返回 null
3. 递归函数逻辑
   1. 如果当前节点比 val 小 root.val < val，说明要往 root 的右子树搜索
   2. 如果当前节点比 val 大 root.val > val，说明要往 root 的左子树搜索
   3. 否则就是当前节点

关键点

• 抓住二叉搜索树的特性
• 左子树的节点都比根节点小
• 右子树的节点都比根节点大
• 并且左右子树都是二叉搜索树

代码

• 语言支持：Java

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null)
            if (val < root.val) root = root.left;
            else if (val > root.val) root = root.right;
            else return root;
        return null;
    }
}

复杂度分析

令 n 为节点个数。

• 时间复杂度：$O(n)$，遍历的节点个数
• 空间复杂度：$O(n)$，最坏情况下递归需要 O(n) 的栈空间。