目录

1. 题目描述

2. 解题分析

3. 代码实现

1. 题目描述

给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

示例 1：

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true

示例 2：

输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

提示:

• 二叉树的节点个数的范围是  [1, 10^4].
• -10^4 <= Node.val <= 10^4
• root 为二叉搜索树
• -10^5 <= k <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

       在Leetcode0001（Leetcode0001: 两数之和(simple, 4种解法)）给出了求两数之和问题的几种基本解法，本题可以沿用，这里采用哈希方法。

        本题进一步追加了一点调味料：树的遍历。只是简单的遍历，所以广度优先搜索还是深度优先搜索在这里没有差别。以下用广度优先搜索方法来实现。

        在广度优先搜索的过程中，用于存储已访问节点的visited用dict实现，这就相当于创建了哈希表。然后再遍历该visited，查询target-x是否也在visited中即可。

        以下代码有一些冗余，原因是我考虑了（题意并没有说清楚）可能存在节点的值重复，且k = 2*val的情况。但是设计了一个测试用例后表明题目拒绝这种情况，报告以下错误：

        'values' must be strictly increasing

        相关部分代码就简单地注释了一下。事实上因为不存在重复的节点值，visited可以用python中的set()实现，不需要用dict()去存储各个val出现次数。

3. 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:

        visited = dict()
        que = collections.deque()

        que.append(root)
        visited[root.val] = 1
        while len(que) > 0:
            node = que.popleft()
            if node.left != None: 
                que.append(node.left)
                #if node.left not in visited:
                visited[node.left.val] = 1
                #else:
                #    visited[node.left.val] += 1

            if node.right != None: 
                que.append(node.right)
                #if node.right not in visited:
                visited[node.right.val] = 1
                #else:
                #    visited[node.right.val] += 1

        if len(visited) < 2:
            return False
        for val in visited:
            #if k == 2* val and visited[val] > 1:
            #    print(k,val,val)
            #    return True
            if k - val in visited and k!= 2*val:
                print(k,val,k - val)
                return True
        
        return False

        说好的封闭两天做两天核酸检测。。。现在第4天了，依然形势不明，好在还可以刷刷leetcode解闷。

        回到主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)https://chenxiaoyuan.blog.csdn.net/article/details/123040889