LeetCode: 700. Search in a Binary Search Tree

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

700. Search in a Binary Search Tree

LeetCode - 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.

思路分析

可以理解成二分查找在二叉搜索树上的应用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-26 14:34:18
 */
public TreeNode searchBST(TreeNode root, int val) {
  if (root == null) {
    return null;
  }
  if (root.val == val) {
    return root;
  }
  return searchBST(val > root.val ? root.right : root.left, val);
}

参考资料

700. 二叉搜索树中的搜索 - 官方题解