Leetcode刷题100天—653. 两数之和 IV - 输入 BST( 二叉树)—day35

雨点打透心脏的1/2处 2022-09-14 00:14 135阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210911170229641][]

#### [653. 两数之和 IV - 输入 BST][653. _ IV - _ BST] ####

难度简单275收藏分享切换为英文接收动态反馈

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

**示例 1：**

![img][]

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

**示例 2：**

![img][img 1]

输入: 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, 104]`.
 *  `-104 <= Node.val <= 104`
 *  `root` 为二叉搜索树
 *  `-105 <= k <= 105`

package 二叉树;
    
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Set;
    
    public class _653_两数之和_IV_输入_BST { 
        public boolean findTarget(TreeNode root, int k) { 
    
    // 解题思路:通过哈希和层序遍历的思想
        	Set<Integer> set=new HashSet<>();
    // 设置队列
        	Queue<TreeNode> queue=new LinkedList<TreeNode>();
    // 入队
        	queue.offer(root);
        	while(!queue.isEmpty()) { 
    // 出队
        		TreeNode node=queue.poll();
        		if (node==null) { 
    				continue;
    			}
    // 判断减去的数是否存在
        		if (set.contains(k-node.val)) { 
    				return true;
    			}
    // 存入集合中
        		set.add(node.val);
    // 存入队列中
        		queue.offer(node.left);
        		queue.offer(node.right);
        		
        	}
        	return false;
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210911170229641]: /images/20220828/d119c057d0004af6a32e948e99277a45.png
[653. _ IV - _ BST]: https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/
[img]: /images/20220828/db73de3f31584c50ba590aff0aad49e6.png
[img 1]: /images/20220828/01f9f989e93e4e219540520b27890af5.png