题目地址(700. 二叉搜索树中的搜索)

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

题目描述

  1. 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
  3. 例如，
  5. 给定二叉搜索树:
  7.         4
  8.        / \
  9.       2   7
  10.      / \
  11.     1   3
  13. 和值: 2
  16. 你应该返回如下子树:
  18.       2     
  19.      / \   
  20.     1   3
  23. 在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

前置知识


公司

  • 暂无

思路

利用 二叉搜索树左小右大的特性 搜索特定的边

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         //方法返回值 返回树节点 参数为节点和要判断的值 直接用原方法
  19.         public TreeNode searchBST(TreeNode root, int val) {
  20.             //中止条件 如果节点等于null 就返回null 如果等于目标值 就返回root
  21.             if (root == null || root.val == val) {
  22.                 return root;
  23.             }
  24.             //单层逻辑 根据二叉搜索树的特性 左边的数小于根节点 右边相反 所以只需要搜索单边 不需要遍历整棵树 
  25.             //当需要搜索单边或者特定边的时候 递归的时候直接return 搜索整颗树的时候不需要return
  26.             if (root.val > val) {
  27.                 return searchBST(root.left, val);
  28.             }else {
  29.                 return searchBST(root.right, val);
  30.             }
  31.         }
  32.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：700. 二叉搜索树中的搜索 - 图1#card=math&code=O%28n%29&id=hOhHn)
  • 空间复杂度：700. 二叉搜索树中的搜索 - 图2#card=math&code=O%28n%29&id=NFRlt)