给定一个二叉搜索树 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, 104]. -104 <= Node.val <= 104root为二叉搜索树-105 <= k <= 105
题解
继续还是二叉搜索树，牢记特性，左小右大，中序遍历后是一个有序递增数组。
那么直接一个中序遍历出来，这样题目就转换成在有个有序递增数组中寻找两个数的和能凑成k，是不是有点眼熟，对的，就是LeetCode刷题 【1】两数之和，先不管之前我们是怎么做的。
那么，按照目前最直观的思路，从数组结尾开始的两个数字尝试相加，假设对应索引为index1,index2，如果这两个位置的值相加比目标值k，大，则尝试将前面一个索引往前移动一位，找一个更小的值相加看是否等于k，一直找到索引为0的位置。如果这两个最大的值相加的合比k小，说明不存在相加了能满足k的情况了。尝试过一轮之后，如果找不到合适的值，则将后一位的索引往前移动一位，继续这个过程。
举例:【1,2,3,4,5,6,7,8】数组
先用7+8尝试，如果大于则用6+8、5+8、4+8尝试，直到1+7尝试，如果没有合适的，则进行下一轮用6+7尝试,5+7、4+7依次尝试。
好了，下面是代码：
class Solution1 {
List<Integer> list = new ArrayList<>();
public boolean findTarget(TreeNode root, int k) {
dfs(root);
int index1 = list.size()-1;
int index2 = index1-1;
while (index2>=0){
if (list.get(index1)+list.get(index2) < k){
return false;
}
while (index2 >= 0 && list.get(index1)+list.get(index2) >= k ){
if (list.get(index1)+list.get(index2) == k){
return true;
}
index2--;
}
index1--;
index2=index1-1;
}
return false;
}
private void dfs(TreeNode node){
if (null==node)return;
dfs(node.left);
list.add(node.val);
dfs(node.right);
}
}而执行的结果告诉了我，问题应该不至于这样
解答成功:
执行耗时:1138 ms,击败了5.24% 的Java用户
内存消耗:39.9 MB,击败了20.04% 的Java用户所以，回到上面的思路中间的过程看下，两个关键点“有序递增数组”，“在这个有序递增数组中寻找一个特定的值”，是不是很自然的就想到了此处应该可以用二分法来处理，此处后续省略。
重新再看下整个思考的过程，就是一个求解a+b=k的过程，其中k预先已给出，a、b值在对二叉树遍历的时候能知道一个，就是当前节点的值。此时问题就变成了再二叉树的所有节点中找另一个值是否存在。此时问题就转换成了，在二叉树遍历过程中，已知了a,已知了k，再在二叉搜索树中搜索(k-a)这个值是否存在，可利用二叉树的左小右大的特性查找。
代码：省略
接下来再进一步，在a+b=k的求解过程中，查找b能否进一步优化呢？答案是可以的，遍历每个节点的时候把值存储到一个hash表中，这样查找b是否存在就可以从原来的搜索二叉树查找转换成hash查找，时间复杂度直接降为O(1)。
class Solution {
HashSet<Integer> hashSet = new HashSet<>();
boolean result = false;
public boolean findTarget(TreeNode root, int k) {
dfs(root,k);
return result;
}
private void dfs(TreeNode node, int k){
if (null==node || result)return;
dfs(node.left,k);
if (!result){
if (hashSet.contains(k-node.val)){
result = true;
}
}
hashSet.add(node.val);
dfs(node.right,k);
}
}
结果
执行耗时:3 ms,击败了83.09% 的Java用户
内存消耗:39.2 MB,击败了79.23% 的Java用户再看看我们之前第一题是怎么做的，LeetCode刷题 【1】两数之和，是不是回到了一样的解法上了。
本题难度设定的是简单题，嗯，本质上就是在原来第一题两数之和的基础上嵌套了一个二叉树遍历。
另外做这题的时候想到的一个点，二叉平衡搜索树的查找搜索过程，和二分法数组查找搜索，这两个算法，本质上是一样的。
发表评论