653. 两数之和 IV - 输入二叉搜索树

🟢   🔖  树 深度优先搜索 广度优先搜索 二叉搜索树 哈希表 双指针 二叉树  🔗 力扣 LeetCode

题目

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, orfalse otherwise.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9

Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28

Output: false

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• -10^4 <= Node.val <= 10^4
• root is guaranteed to be a valid binary search tree.
• -10^5 <= k <= 10^5

题目大意

给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 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

解题思路

这道题目要求在二叉树中找到是否存在两个节点，它们的值之和等于给定的数值 k。可以使用 深度优先搜索 (DFS) 配合 哈希集合 (Set) 来高效地解决这个问题。

1. 初始化一个空的哈希集合 set，用于存储已访问的节点值。

2. 使用深度优先搜索（DFS）遍历整棵树。通过递归访问每一个节点，并在每个节点处检查是否能够找到符合条件的两个值。

   • 由于需要查找两个节点的值之和等于 k，当访问到一个节点时，检查 k - node.val 是否已经出现在哈希集合中。
   • 如果 k - node.val 已经在哈希集合中，说明找到了满足条件的两个节点，它们的值之和等于 k，此时返回 true。
   • 否则，将当前节点的值加入集合中，继续遍历其左子树和右子树。

3. 从根节点调用 dfs，如果找到符合条件的节点，则返回 true，否则返回 false。

复杂度分析

• 时间复杂度：O(n)，每个节点只被访问一次。
• 空间复杂度：O(n)，哈希集合需要存储每个节点的值，最坏情况下要存储所有节点的治。

代码

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {boolean}
 */
var findTarget = function (root, k) {
	let set = new Set(); // 用于存储已访问的节点值

	// 深度优先搜索 (DFS) 函数
	const dfs = (node) => {
		if (!node) return false; // 如果当前节点为空，返回 false
		if (set.has(k - node.val)) {
			// 如果存在一个已访问的值，使得 k - node.val == 目标值
			return true;
		}
		set.add(node.val); // 将当前节点的值加入集合
		// 递归遍历左子树或右子树
		return dfs(node.left) || dfs(node.right);
	};

	return dfs(root); // 从根节点开始进行 DFS
};

相关题目

题号	标题	题解	标签	难度	力扣
1	两数之和	[✓]	数组 哈希表	🟢	🀄️ 🔗
167	两数之和 II - 输入有序数组	[✓]	数组 双指针 二分查找	🟠	🀄️ 🔗
170	两数之和 III - 数据结构设计 🔒	[✓]	设计 数组 哈希表 2+	🟢	🀄️ 🔗
1214	查找两棵二叉搜索树之和 🔒		栈 树 深度优先搜索 4+	🟠	🀄️ 🔗