0700. Search in a Binary Search Tree - chasel2361/leetcode GitHub Wiki

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.

For example, Given the tree:
4
/ \
2 7
/ \
1 3
And the value to search: 2
You should return this subtree:
2
/ \
1 3
In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.
Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.

這題要求的是BST的搜尋，概念其實沒有很困難，只要將節點逐一提取出來與目標對照，若節點值比目標大，便將節點往左子樹移動，反之則往右子樹移動，相等的話就是目標，如果走到盡頭就是無結果，寫作程式如下。

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or val == root.val: return root

        while root.val != val:
            node = root.val
            if node > val:
                root = root.left
            else:
                root = root.right
                
            if not root: return None
        return root

這樣寫的時間複雜度是 O(N)，空間複雜度是 O(1)。

另外還可以寫成遞迴的形式，如果當前節點值小於目標，就重新呼叫函式輸入右子樹與目標值；反之則輸入左子樹與目標值

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or val == root.val: return root
            
        if root.val < val: 
            return self.searchBST(root.right, val)
        else: 
            return self.searchBST(root.left, val)

這樣寫的時間複雜度是 O(N)，空間複雜度是 O(N)，因為每呼叫一次函式都會耗損空間。