今日題目

題目連結：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

上圖是在跑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：結束後的下一步