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

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