如何在二叉搜索树中查找一个节点？

推荐答案

// www.javascriptcn.com code example
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def searchBST(root: TreeNode, val: int) -> TreeNode:
    if not root or root.val == val:
        return root
    if val < root.val:
        return searchBST(root.left, val)
    else:
        return searchBST(root.right, val)

本题详细解读

1. 二叉搜索树（BST）的特性

二叉搜索树是一种特殊的二叉树，具有以下特性：

• 左子树上的所有节点的值都小于根节点的值。
• 右子树上的所有节点的值都大于根节点的值。
• 左右子树也分别是二叉搜索树。

2. 查找节点的思路

在二叉搜索树中查找一个节点，可以利用其特性进行递归或迭代查找：

• 如果当前节点为空，说明未找到目标节点，返回 None。
• 如果当前节点的值等于目标值，返回当前节点。
• 如果目标值小于当前节点的值，递归查找左子树。
• 如果目标值大于当前节点的值，递归查找右子树。

3. 代码实现

• TreeNode 类定义了二叉搜索树的节点结构。
• searchBST 函数实现了递归查找：
  • 如果 root 为空或 root.val 等于目标值 val，直接返回 root。
  • 如果 val 小于 root.val，递归查找左子树。
  • 否则，递归查找右子树。

4. 时间复杂度

• 平均情况下，时间复杂度为 O(log n)，其中 n 是树中节点的数量。
• 最坏情况下（树退化为链表），时间复杂度为 O(n)。

5. 空间复杂度

• 递归调用栈的深度取决于树的高度，平均情况下为 O(log n)，最坏情况下为 O(n)。

6. 迭代实现（可选）

def searchBST(root: TreeNode, val: int) -> TreeNode:
    while root and root.val != val:
        root = root.left if val < root.val else root.right
    return root

• 迭代实现避免了递归调用栈的开销，空间复杂度为 O(1)。