LeetCode: 700. Search in a Binary Search Tree

题目

原题地址：https://leetcode.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 特性加速查找

根据 BST 的特性可以知道，一个节点的所有左侧子节点的值都要小于或等于该节点值，所有右侧子节点的值都要大于或等于该节点的值。 可以基于这个特性加速查找：

  1. 如果要查找的值等于当前节点的值，当前节点即为要查找的节点。
  2. 如果要查找的值小于当前节点的值，则继续在左侧子节点中进行查找。
  3. 如果要查找的值大于当前节点的值，则继续在右侧子节点中进行查找。

相应的 Python 代码类似下面这样:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if root is None:
            return

        if val == root.val:
            return root
        if val > root.val:
            return self.searchBST(root.right, val)
        if val < root.val:
            return self.searchBST(root.left, val)

Comments