当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.700.Search in a Binary Search Tree 在BST中搜索

LeetCode.700.Search in a Binary Search Tree 在BST中搜索

题目描述

700 Search in a Binary Search Tree
https://leetcode-cn.com/problems/search-in-a-binary-search-tree/

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example,

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2
You should return this subtree:

      2
     / \
    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.


解题过程

在二叉搜索树BST中搜索,也就是二分搜索。
时间复杂度 O(logn),空间复杂度 O(1)

private static class SolutionV2020 {
    public TreeNode searchBST(TreeNode root, int val) {
        if (null == root) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        if (root.val > val) {
            return searchBST(root.left, val);
        }
        return searchBST(root.right, val);
    }
}

GitHub代码

algorithms/leetcode/leetcode/_700_SearchBinarySearchTree.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_700_SearchBinarySearchTree.java


上一篇 LeetCode.783.Minimum Distance Between BST Nodes BST的最小差值

下一篇 LeetCode.124.Binary Tree Maximum Path Sum 二叉树的最大路径和

阅读
评论
227
阅读预计1分钟
创建日期 2020-02-02
修改日期 2020-02-02
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论