Day 17：700. Search in a Binary Search Tree

今日题目

题目连结：700. Search in a Binary Search Tree
题目主题：Tree, Binary Search Tree, Binary Tree

简单说说 Binary Search Tree

昨天分享了 Binary Search Tree 的原则，今天来説说Binary Search Tree 是怎麽快速找到目标值的。

Binary Search Tree 的原则是越左边的值越小、越右边的值越大，也就是説根节点的左半部一定都小於根节点、右半部一定都大於根节点，如果要搜寻一个值，会从根节点开始走，运作过程如下图：

范例： tree = [5, 2, 6, 1, 3, null, 8]

目标值：8

目标值大於根节点，直接往右走，走到第二层是 6 ，目标值 8 还是大於 6 ，所以继续往右走，最终搜寻到这棵树里面有 8。

目标值：3

目标值小於根节点，直接往左走，走到第二层是 2 ，目标值 3 大於 2 ，所以接着往右走，最终搜寻到这棵树里面有 3。

目标值：10

目标值大於根节点，直接往右走，走到第二层 6 ，目标值 10 还是大於 6 ，所以继续往右走，第三层是 8 发现 10 还是比较大，所以又往下一层右边走，但发现已经没有节点了，所以可以下结论这棵树里面没有 10 这个值。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目会给一个Binary Search Tree及一个目标值，目标是确认这个目标值是否在这颗Binary Search Tree中，若有出现的话，回传目标值所在的TreeNode，若没找到回传 Null 代表没有。

约束：

• 这是一颗Binary Search Tree
• 树的节点总数范围在[1, 5000]
• 1 <= Node.val <= 10的7次方
• 1 <= val <= 10的7次方

范例1

输入：root = [4,2,7,1,3], val = 2
输出：[2, 1, 3]
解说：目标值 2 在 root 里面有出现，因此回传 2 这个TreeNode，参考上图。

范例2

输入：root = [4,2,7,1,3], val = 5
输出：[]
解说：目标值 5 在 root 里面找不到，因此回传null

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 写一个递回方法，每次使用传进一个TreeNode及目标值。
2. 每次进入方法会检查以下：
   • 目前是否有节点，若没有节点代表这棵树不存在目标值，回传 Null 结束。
   • 目前节点的值是否与目标值相同，若相同回传目前节点结束。
   • 目标值若小於目前节点的值，往目前节点的左边子节点走。
   • 目标值若大於目前节点的值，往目前节点的右边子节点走。

图解过程

范例：root = [5, 2, 6, 1, 3, null, 8]
目标值：3

如上图所示，目标值为 3 小於根节点的值 5 先往左走，走到第二层目标值 3 大於目前节点的值 2 ，所以接着往右走，最终搜寻到这棵树里面有 3 这个节点，最终回传这个节点结束。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # 若没有节点，代表走到树的底且目标值不在树中
        if root == None: return None
        # 若有与目标值相同值的节点，代表找到目标回传这个节点
        if root.val == val: return root
        
        # 若值大於目前节点的值，往下层右边节点走
        if val > root.val:
            return self.searchBST(root.right, val)
        # 若值小於目前节点的值，往下层左边节点走
        if val < root.val:
            return self.searchBST(root.left, val)

希望您今天能了解到...

1. Binary Search Tree 搜寻值
2. 700. Search in a Binary Search Tree 的解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：501. Find Mode in Binary Search Tree