两数之和 IV - 输入二叉搜索树
难度:
标签:
题目描述
给定一个二叉搜索树 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, 104]. -104 <= Node.val <= 104- 题目数据保证，输入的
root是一棵 有效 的二叉搜索树 -105 <= k <= 105
代码结果
运行时间: 40 ms, 内存: 18.1 MB
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
// 思路：
// 1. 使用中序遍历将 BST 转换成有序 List。
// 2. 使用 Stream API 和双指针法在有序 List 中寻找两个数，使它们的和等于 k。
public class Solution {
public boolean findTarget(TreeNode root, int k) {
List<Integer> nums = new ArrayList<>();
inorder(root, nums);
return nums.stream().anyMatch(n -> nums.contains(k - n));
}
private void inorder(TreeNode root, List<Integer> nums) {
if (root == null) {
return;
}
inorder(root.left, nums);
nums.add(root.val);
inorder(root.right, nums);
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}解释
方法:
该题解使用深度优先搜索（DFS）遍历二叉搜索树，同时维护一个哈希集合 visited 来保存已访问过的节点值。对于每个访问的节点，计算其与目标值 k 的差值 complement，然后检查 complement 是否在 visited 中，如果在，则说明找到了两个节点的和等于 k，返回 True。如果当前节点的左右子树递归搜索都没有找到满足条件的节点对，则返回 False。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么选择使用深度优先搜索（DFS）而不是广度优先搜索（BFS）来解决这个问题？两者在性能上会有什么不同？
▷🦆
题解的算法中是否考虑了节点值可能重复的情况？例如在二叉搜索树中，两个相同的值是否会影响 `visited` 集合的查找结果？
▷相关问题
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示：
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers按 非递减顺序 排列-1000 <= target <= 1000- 仅存在一个有效答案