在二叉搜索树中搜索 - 为什么这段代码有效？

Question

我正在研究 LeetCode 问题 Search in a Binary Search Tree:

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

[...]

Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []

我不确定为什么下面的代码可以在 Python:

中运行

def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    #base case
    if not root: return None
    if root.val == val: return root
    
    #recursion relation
    if val > root.val:
       return self.searchBST(root.right, val)
    else:
       return self.searchBST(root.left, val)

具体来说，在问题中它说（1）如果树为空，那么我们需要return，（2）如果值不在树中，我们需要return 空

那么if not root: return None这行代码，是否迎合了（1）？我们不是必须 return [] 吗？

Answer 1

in the question it says (1) if Tree is null, then we need to return [], (2) If value is not in the tree, we need to return null

这不完全正确。它说我们需要 return null，但在示例中它表示输出为 [].

这是可以理解的，这会导致混乱，但应该注意的是，LeetCode 将输入和输出格式化（序列化）为列表（JSON 表示法），即使实际输入和输出 你的函数处理的不是列表。该函数获取一个节点实例作为参数（或None），函数是对return这样一个引用（或None）。

LeetCode 框架负责在调用函数之前将 text-based 输入转换为节点引用，并在处理函数 return 的值时执行相反的操作。特别是，当您的函数 returns None 时，它将序列化为 [] —— 表示一棵空树。

在二叉搜索树中搜索 - 为什么这段代码有效？

Search in Binary Search Tree - why this code works?

python

tree

binary-search-tree

Example 2: