700. Search in a Binary Search Tree

昨天提到鏈結串列（Linked List）的題目，今天就挑了一題「樹（Tree）」的題目，還是經典的二元搜尋樹（BST，Binary Search Tree）。二元搜尋樹會根據資料數值加入的先後順序與大小依序插入，小的往左邊放、大的往右邊放，最終形成一顆二元樹，能夠有效用於查詢情境。對於一個二元搜尋樹的「建立」、「新增」、「刪除」或「查詢」
都是基本的操作，不過當遇到複雜的樹結構，就多了一層的挑戰。

先看一下題目描述

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

再搭配範例理解題目

• Example 1:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

• Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []

這個題目給一個 root，並且建構成一個二元樹，要求從二元樹中找到 val 的值，並且回傳包含 val 作為 root 的子樹。

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：迴圈迭代法

第一種方法就是直覺的利用二元搜尋樹的特性一個一直找，目標值比較小就往左找、目標值比較小就往右找，直到找到該數值即回傳。題目中要求「回傳包含 val 作為 root 的子樹」其實不用特別處理，因為樹本身就是一個樹狀結構，只要專注找到數值就好。

那我們先用 Python 實作看看

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: 
        while root:
            if root.val == val:
                return root
            elif root.val > val:
                root = root.left
            elif root.val < val:
                root = root.right
        return root

也可以用 JavaScript 復刻一次

var searchBST = function(root, val) {
    while(root.val != null){
        if (root.val === val)
            return root
        else if (val < root.val)
            root = root.left
        else 
            root = root.right
    }
    return root
};

原本寫法的條件判斷比較複雜，可以利用三元運算的方式做簡化：

# Python
while root:
  root = root.left if val < root.val else root.right
return root

# JavaScript
while(root !== null){
  root = val < root.val ? root.left : root.right;
}
return root

方法 ②：遞迴（recursion）

第二種方法是遞迴（recursion），概念是「判斷這一層是否符合條件，否則就往兩個子樹各別往下層找」，然後直到找到為止直接回傳。其實以樹來說，遞迴的方法反而比較直覺，只要設定到起始與終止條件，設定就讓遞迴自己依序完成。

那我們先用 Python 實作看看

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

也可以用 JavaScript 復刻一次

var searchBST = function(root, val) {
    if(!root) return null
    if(root.val === val) return root
    return searchBST(root.left,val) || searchBST(root.right,val)
};

反思沉澱

從鏈結串列（Linked List）到樹（Tree）或二元搜尋樹（BST，Binary Search Tree），是一種從線性到非線性的概念。線性指的是只會有下一個可能，終究只會有一條路徑；非線性的話則可能有不同的分岔，可能會產生出兩條以上的可能路徑。以二元樹來說，每一個點最多可能會有兩個點的下一個可能，因此可能就會有「不同往下找」的做法，應該先找完同一層的，還是先找到最底再回頭找，就會有許多的變化可以玩。對於一個容器「建立」、「新增」、「刪除」或「查詢」都是基本的操作，不過當遇到複雜的鏈結串列或樹結構，就多了一層的挑戰。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 701. Insert into a Binary Search Tree

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。