AlgoPressAppearance
0653-两数之和IV-输入BST
https://leetcode.cn/problems/two-sum-iv-input-is-a-bst
给定一个二叉搜索树 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, 10^4].
-10^4<= Node.val <= 10^4
root为二叉搜索树
-10^5<= k <= 10^5
思路1：哈希表
深度搜索，是用字典储存已经访问过的值，如果发现 k - node.val = 储存的值，则找到，否则返回没找到。 思路和两数之和一样
参考代码
csharp
public class Solution {
Dictionary<int,int> dict = new Dictionary<int,int>();
public bool FindTarget(TreeNode root, int k) {
if(root == null){
return false;
}
int target = k - root.val;
if(dict.ContainsKey(target)){
return true;
}
dict.Add(root.val, root.val);
return FindTarget(root.left, k) || FindTarget(root.right, k);
}
}
思路2：中序遍历
csharp
public class Solution {
//平衡二叉树的中序遍历，就是递增数组，用一次个和最后一个相加看是否是结果
private List<int> list = new List<int>();
private void dfs(TreeNode root){
if(root == null){
return;
}
dfs(root.left);
list.Add(root.val);
dfs(root.right);
}
public bool FindTarget(TreeNode root, int k) {
dfs(root);
int left=0;
int right = list.Count-1;
while(left < right){
int sum = list[left]+list[right];
if(sum == k){
return true;
}
else if(sum > k){
right--;
}
else{
left++;
}
}
return false;
}
}
复习：20220616
csharp
public class Solution {
bool result = false;
private Dictionary<int,int> dict = new Dictionary<int,int>();
private void dfs(TreeNode root, int k){
if(root == null){
return;
}
if(dict.ContainsKey(k-root.val)){
result = true;
return;
}
else{
dict.Add(root.val,1);
}
dfs(root.left,k);
dfs(root.right,k);
}
public bool FindTarget(TreeNode root, int k) {
dfs(root,k);
return result;
}
}