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

推荐答案

-- -------------------- ---- -------
----- ---------
    --- -------------- ------ ---------- ------------
        -------- - ---
        --------- - ----
        ---------- - -----

--- --------------- --------- ---- ---- -- ---------
    -- --- ---- -- -------- -- ----
        ------ ----
    -- --- - ---------
        ------ -------------------- ----
    -----
        ------ --------------------- ----

本题详细解读

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)。