iT邦幫忙

2021 iThome 鐵人賽

DAY 29
0
Software Development

我在刷LeetCode時邂逅了Python系列 第 29

Day 29:653. Two Sum IV - Input is a BST

今日題目

題目連結:653. Two Sum IV - Input is a BST
題目主題:Hash Table, Two Pointers, Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree

今天是最後一個題目了,接著Hash Table,找了一個小小的綜合題,可以練習到 Traversal、Queue、Tree 等等的概念,都是本系列文有提過的概念,雖然用 Depth-First Search 也可以解題,但這次會用 Breadth-First Search 的方式來分享解題方法,平常感覺比較少用這個方法解題,這邊我們最後再來練習一下。


題目解說

建議可以看看LeetCode原本的題目說明,這邊是用我的方式說明題目,參考就好。

題目會給一個 Binary Search Tree,目的是要在這棵樹裡面確認有沒有相加為 k 的兩個數字,若出現相加為 k 的兩個數字最終回傳 True,若沒出現則回傳 False。

約束:

  • 樹的節點總數範圍在 [1, 10的4次方]
  • -10的4次方 <= Node.val <= 10的4次方
  • 這棵樹符合 Binary Search Tree 的原則
  • -10的5次方 <= k <= 10的5次方

範例1

輸入: root = [5,3,6,2,4,null,7], k = 9
輸出: true
解說: root 裡面有 5 跟 4 可相加為 9,輸出 True。

範例2

輸入: root = [5,3,6,2,4,null,7], k = 28
輸出: false
解說: root 裡面沒有兩個數字能相加為 28,輸出 False。

範例3

輸入: root = [2,1,3], k = 4
輸出: true
解說: root 裡面有 1 跟 3 可相加為 4,輸出 True。

範例4

輸入: root = [2,1,3], k = 1
輸出: false
解說: root 中任兩個數字相加都大於 1,輸出 False。

範例5

輸入: root = [2,1,3], k = 3
輸出: true
解說: root 裡面有 2 跟 1 可相加為 3,輸出 True。

建議到這邊先停下來,嘗試自己解解看,若沒有想法可再繼續走下去。


解題的想像

文字描述

  1. 先準備實作 Hash Table 時需要的 map 及實作 Level-Order Traversal 用的 Queue。
  2. 用Level-Order Traversal的方式,來走過所有節點。
  3. 每次拿一個節點,檢查是否已經出現在 map 中,若有代表找到可相加成 k 的兩個數字,直接回傳 True 結束。若沒有會用 (k - 目前節點的值) 當作 key 紀錄在 map 中。
  4. 若所有節點走過,都沒有找到能相加成 k 的兩個數字,回傳 False 結束。

圖解過程

範例: root = [6, 4, 8, 2, 5], k = 8

https://ithelp.ithome.com.tw/upload/images/20211013/20141336xRWLAFJe4v.png

上圖是在跑Level-Order Traversal的過程,下方的圓角長方是一個Hash Table,每走一個節點都會拿現在節點的值來確認是否有出現在 Hash Table 中。

step1 ~ step3 是沒有出現在 Hash Table 的狀況,所以會將 k - 目前節點的值當作 key,節點值當 value。

step4 的 2 有在 Hash Table 中找到,代表有找到兩個數字相加等於 k 的兩個數字,2 + 6 = 8,範例最後會回傳 True。

若因為沒想法而走到這邊,建議看完想像以後再給自己一次機會試一次。


程式碼撰寫

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        map = {}
        queue = deque()
        queue.append(root)

        while len(queue) > 0:
            node = queue.popleft()
            if node.val in map:
                return True
            key = k - node.val
            map[key] = node
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        return False

希望您今天能瞭解到...

  1. 複習 Tree、Traversal、Hash Table 等等相關概念
  2. 653.Two Sum IV - Input is a BST 的解題方法

若內容有什麼問題或建議歡迎一起交流:)
感謝您今天願意花時間看完這篇文章~~~~

Next:結束後的下一步


上一篇
Day 28:1. Two Sum
下一篇
Day 30:結束後的下一步
系列文
我在刷LeetCode時邂逅了Python30

1 則留言

0
juck30808
iT邦新手 1 級 ‧ 2021-10-14 12:09:19

恭喜即將邁入完賽~/images/emoticon/emoticon08.gif

Mr. YA iT邦新手 5 級 ‧ 2021-10-14 21:01:28 檢舉

哈哈 謝謝您/images/emoticon/emoticon41.gif

我要留言

立即登入留言