两数之和为k(在SBT树中判断是否存在)
https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/
两数之和为k(在SBT树中判断是否存在)
1Solution 递归(n次) Accepted 时空复杂度 O(nlogn) O(n)
class Solution {
static int maxn = 10005,len = 0;
static int a[] = new int[maxn];
static void dfs(TreeNode root) {
if(root==null) return;
a[len++] = root.val;
dfs(root.left);
dfs(root.right);
}
static boolean solve(TreeNode root, int p) {
if(root==null) return false;
if(root.val==p) return true;
if(root.val>p)
return solve(root.left,p);
return solve(root.right,p);
}
public boolean findTarget(TreeNode root, int k) {
len = 0;
dfs(root);
if(len<=1) return false;
boolean flag = false;
for(int i = 0; i < len; ++i) {
if(k-a[i]==a[i]) continue;
flag = solve(root,k-a[i]);
if(flag) break;
}
return flag;
}
}
2Solution <递归(官方1)> Accepted / Used 时空复杂度 O(n) O(n)
// 边遍历边加入元素, 应为x-val与val是对称的,遍历到当期元素root,使用set.contains(k-root.val)就可以了
//java 的contains() 是O(1)
class Solution {
static Set set = new HashSet();
static boolean f(TreeNode root,int k){
if(root==null) return false;
if(set.contains(k-root.val))
return true;
set.add(root.val);//别忘了加入元素
return f(root.left,k)||f(root.right,k);
}
public boolean findTarget(TreeNode root, int k) {
set.clear();
return f(root,k);
}
}
3Solution <递归(官方)> Accepted / Used 时空复杂度 O(n) O(n)
官方题解:https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/solution/liang-shu-zhi-he-iv-shu-ru-bst-by-leetco-b4nl/ 题解二:广度优先搜索 + 哈希表 题解三:深度优先搜索 + 中序遍历 + 双指针
