（Java）leetcode-653 Two Sum IV - Input is a BST (两数之和 IV - 输入 BST)

墨蓝 2023-02-16 01:57 27阅读 0赞

# 题目描述 #

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk_size_16_color_FFFFFF_t_70 1]

# 思路 #

参考[leetcode-1 Two Sum ][leetcode-1 Two Sum]。经典的第一题中，由于需要记录符合的数据位置，所以使用hashMap来记录已经遍历过的数据。而此题中无须记录位置，因此使用hashSet即可。

## 代码 ##

class Solution { 
        public boolean findTarget(TreeNode root, int k) { 
            HashSet<Integer> set = new HashSet<>();
            return dfs(root, set, k);
        }
        
        public boolean dfs(TreeNode root, HashSet<Integer> set, int k){ 
            if(root == null) return false;
            if(set.contains(k - root.val)) return true;
            set.add(root.val);
            return dfs(root.left, set, k) || dfs(root.right, set, k);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200607154654220.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200607154703662.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk=,size_16,color_FFFFFF,t_70
[leetcode-1 Two Sum]: https://blog.csdn.net/z714405489/article/details/88615195