700. Search in a Binary Search Tree

700. Search in a Binary Search Tree

如果說題目只是問「樹」中是否存在一個節點有某個值，那基本上我們就是從根去找，如果不是答案，再繼續去左、右子樹找。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or root.val == val:
            return root
        return self.searchBST(root.left, val) or self.searchBST(root.right, val)

但是如果是 BST ，就可以利用 BST 的特性，去做二分搜索，提高演算法的效率。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or root.val == val:
            return root
        if root.val > val:
            return self.searchBST(root.left, val)
        elif root.val <= val:
            return self.searchBST(root.right, val)