iT邦幫忙

2024 iThome 鐵人賽

DAY 13
0
佛心分享-刷題不只是刷題

[30天LeetCode挑戰] 每天一點演算法,讓技巧融會貫通系列 第 13

[Day13] 關於二元樹、BST、Quick Sort、Merge Sort的刷題筆記(108, 700)

  • 分享至 

  • xImage
  •  

LeetCode 108: Convert Sorted Array to Binary Search Tree

題目要求將一個升序排列的數組轉換為一棵高度平衡的二元搜尋樹。

二元搜尋樹的特點:

  • 左子樹的所有節點值都小於根節點的值。
  • 右子樹的所有節點值都大於根節點的值。

高度平衡樹的定義:

  • 一棵二元樹中的每個節點,左右子樹的高度差不能超過 1。這樣可以確保樹的深度盡可能的小,以達到更好的查找效率。

解題思路:

  1. 中間元素作為根節點:由於數組是有序的,我們可以選擇數組的中間元素作為根節點,這樣可以保證左右子樹的節點數目差不會太大,從而達到平衡。
  2. 遞迴構建子樹:選定根節點後,左半部分的數組對應左子樹,右半部分的數組對應右子樹。我們對每個部分繼續遞迴地構建二元搜尋樹。

程式碼:

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None  # 如果數組為空,返回空樹

        # 選擇中間元素作為根節點
        mid = len(nums) // 2
        root = TreeNode(nums[mid])

        # 遞迴構建左子樹和右子樹
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])

        return root

解題步驟:

  1. 基礎檢查:首先檢查數組是否為空,若為空,則返回空樹。
  2. 選擇根節點:取數組的中間元素作為根節點,這樣可以保證平衡。
  3. 遞迴構建左右子樹:對於中間元素左邊的部分,繼續遞迴構建左子樹;對於右邊的部分,構建右子樹。
    最終返回根節點,代表整個樹。

LeetCode 700: Search in a Binary Search Tree

這個題目要求我們在一棵二元搜尋樹中查找一個指定的值,並返回包含該值的節點。如果該值不存在,則返回 None

解題思路

因為二元搜尋樹的特性:

  • 左子樹的所有節點值都小於根節點的值。
  • 右子樹的所有節點值都大於根節點的值。

因此,我們可以根據這些特性來進行搜索:

  1. 如果目標值小於當前節點的值,我們應該在左子樹中繼續搜索。
  2. 如果目標值大於當前節點的值,我們應該在右子樹中繼續搜索。
  3. 如果目標值等於當前節點的值,我們便找到了所需的節點,直接返回該節點。

程式碼

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # 基本情況:當節點為空或者找到目標值時,返回當前節點
        if root is None or root.val == val:
            return root

        # 如果目標值小於當前節點值,繼續在左子樹搜索
        if val < root.val:
            return self.searchBST(root.left, val)

        # 如果目標值大於當前節點值,繼續在右子樹搜索
        return self.searchBST(root.right, val)

解題步驟

  1. 基礎檢查:如果當前節點為空,或者我們已經找到了目標值,則直接返回當前節點。
  2. 搜索左子樹或右子樹:
    • 如果目標值小於當前節點的值,遞迴搜索左子樹。
    • 如果目標值大於當前節點的值,遞迴搜索右子樹。
  3. 返回結果:當找到目標節點時返回該節點,否則返回 None 表示沒有找到。

上一篇
[Day12] 關於二元樹、BST、Quick Sort、Merge Sort的刷題筆記(111, 230)
下一篇
[Day14] 關於二元樹、BST、Quick Sort、Merge Sort的刷題筆記(938, 701)
系列文
[30天LeetCode挑戰] 每天一點演算法,讓技巧融會貫通30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言