一、问题描述

给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回NULL。

二、方案一：递归法

1、思路

由于二叉搜索树的特点是左子树的值小于根节点，右子树的值大于根节点，我们可以利用这一特性进行递归搜索。

• 如果当前节点为空，返回NULL。
• 如果当前节点的值等于目标值，返回当前节点。
• 如果目标值小于当前节点的值，递归搜索左子树。
• 如果目标值大于当前节点的值，递归搜索右子树。

2、代码实现

func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil || root.Val == val {
        return root
    }
    if val < root.Val {
        return searchBST(root.Left, val)
    }
    return searchBST(root.Right, val)
}

3、复杂度分析

• 时间复杂度：O(H)，其中H是树的高度。
• 空间复杂度：O(H)，递归栈的深度。

三、方案二：迭代法

1、思路

迭代法通过循环来实现递归的逻辑。

• 从根节点开始，循环执行以下操作：
  • 如果当前节点为空或其值等于目标值，返回当前节点。
  • 如果目标值小于当前节点的值，将当前节点设置为左子节点。
  • 如果目标值大于当前节点的值，将当前节点设置为右子节点。

2、代码实现

func searchBST(root *TreeNode, val int) *TreeNode {
    for root != nil && root.Val != val {
        if val < root.Val {
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return root
}

3、复杂度分析

• 时间复杂度：O(H)，其中H是树的高度。
• 空间复杂度：O(1)，不需要额外的空间。

四、总结

递归法和迭代法都能有效地解决这个问题。递归法代码更简洁，但迭代法在空间复杂度上可能更有优势，因为它不需要递归栈空间。具体使用哪种方法取决于个人偏好和具体问题的需求。