700. 二叉搜索树中的搜索

leecode原题

题目

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

• 数中节点数在 [1, 5000] 范围内
• 1 <= Node.val <= 107
• root 是二叉搜索树
• 1 <= val <= 107

解题思路

思路

二叉搜索树是一个有序树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树

这就决定了，二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样。

核心解法:
根据二叉树的特性, 可以比较根节点和目标值的大小关系，如果相等即找到目标树，如果大于目标值，则递归找左子树，如果小于目标值，则递归找右子树。

实现

源码

func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return nil
    }
    // 找到目标树
    if root.Val == val {
        return root
    }

    // 左子树非空，并且左子树根节点大于目标值(左子树值均小于根节点值)
    if root.Left != nil && root.Val > val {
        return searchBST(root.Left, val)
    }
    // 右子树非空，并且右子树根节点小于于目标值(右子树值均大于根节点值)
    if root.Right != nil && root.Val < val {
        return searchBST(root.Right, val)
    }
    return nil
}