653 两数之和 IV - 输入 BST（递归、哈希表）

快来打我* 2022-08-29 09:41 114阅读 0赞

**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

**示例 3：**

输入: root = \[2,1,3\], k = 4  
输出: true

**示例 4：**

输入: root = \[2,1,3\], k = 1  
输出: false

**示例 5：**

输入: root = \[2,1,3\], k = 3  
输出: true

**提示:**

二叉树的节点个数的范围是 \[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. 思路分析：**

分析题目可以知道当前的树是二叉搜索树，而二叉搜索树的中序遍历是有序的，所以我们在中序遍历的时候其实知道的是一维数组，所以本质上是判断在一维数组中是否存在两个数的和等于目标值，这个问题我们可以使用**哈希表**来解决，我们可以在中序遍历的时候将当前遍历的节点值存储到哈希表中，并且在哈希表中寻找k - root.val是否存在，如果存在说明找到了两个数的和等于目标值的方案直接返回True即可，不存在则继续往下找。

**3. 代码如下：**

class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
    
    
    class Solution:
        def dfs(self, root: TreeNode, k: int, dic: dict):
            if not root: return False
            # 当遍历的时候发现找到了两数之和等于目标值那么返回True不用往下找了
            if self.dfs(root.left, k, dic): return True
            x = root.val
            if k - x in dic: return True
            # 将当前的根节点存储到哈希表
            dic[x] = 1
            return self.dfs(root.right, k, dic)
    
        # 在中序遍历的时候使用一个哈希表来检查
        def findTarget(self, root: TreeNode, k: int) -> bool:
            dic = dict()
            return self.dfs(root, k, dic)