iT邦幫忙

2021 iThome 鐵人賽

DAY 11
1
Software Development

LeetCode 雙刀流:Python x JavaScript系列 第 11

LeetCode 雙刀流:700. Search in a Binary Search Tree

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

舉一反三看看相似題

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


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


上一篇
LeetCode 雙刀流:206. Reverse Linked List
下一篇
LeetCode 雙刀流:144. Binary Tree Preorder Traversal
系列文
LeetCode 雙刀流:Python x JavaScript30

2 則留言

0
Ellen Lee
iT邦新手 5 級 ‧ 2021-09-26 22:45:22

你竟然幫自己做了主視覺!!

WeiYuan iT邦新手 4 級 ‧ 2021-09-26 23:07:57 檢舉

身為一個業餘小編,做點圖也是很合理的

0
TD
iT邦新手 5 級 ‧ 2021-09-28 09:43:38

謝謝維元老師分享~~

--
小小建議,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)
};
WeiYuan iT邦新手 4 級 ‧ 2021-09-28 11:04:39 檢舉

應該要的!已改

我要留言

立即登入留言