TwoSumIV_InputIsABST [source code]
public class TwoSumIV_InputIsABST {
static
/******************************************************************************/
public class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet<>();
Queue<TreeNode> q = new LinkedList<>();
if (root == null)
return false;
q.add(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
if (!set.add(k - node.val))
return true;
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
}
}
return false;
}
}
/******************************************************************************/
public static void main(String[] args) {
TwoSumIV_InputIsABST.Solution tester = new TwoSumIV_InputIsABST.Solution();
}
}
这个题目就是把array换成了BST, 一个很小的变种. 在iteration的面前, 并没有什么区别;
另外注意这里题目的要求, 最后只要求你返回一个boolean, 而不是index, 所以不需要用HashMap了;
随便用BFS写了一个, 当做是玩了. 最后的速度不是特别理想: 37ms (50%). 不过也没有什么太大的参考性;
editorial1, 简单的DFS版本:
public class Solution {
public boolean findTarget(TreeNode root, int k) {
Set < Integer > set = new HashSet();
return find(root, k, set);
}
public boolean find(TreeNode root, int k, Set < Integer > set) {
if (root == null)
return false;
if (set.contains(k - root.val))
return true;
set.add(root.val);
return find(root.left, k, set) || find(root.right, k, set);
}
}
虽然说我认为BFS可以有一个premature exit所以可能会快一些, 但实际上最后的结果并不是这样, recursion的优化还是可怕;
editorial2就是BFS;
上面两个做法其实都是没有用到BST的性质; 这里也是我的疏忽了; 那么BST的性质怎么利用呢?
这个是editorial3的做法:
public class Solution {
public boolean findTarget(TreeNode root, int k) {
List < Integer > list = new ArrayList();
inorder(root, list);
int l = 0, r = list.size() - 1;
while (l < r) {
int sum = list.get(l) + list.get(r);
if (sum == k)
return true;
if (sum < k)
l++;
else
r--;
}
return false;
}
public void inorder(TreeNode root, List < Integer > list) {
if (root == null)
return;
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
}
}
因为是BST, 所以InOrder traverse出来的就是一个sorted的, 然后可以用那个sorted的2sum的解法来做, 理论上的速度比较快;
这个答案应该是这个题目的标准答案, 因为用到了BST的性质; 有没有可能直接在DFS的过程中就使用BST的性质, 不需要serialization呢? 好像不太可能, 因为你利用BST的性质来DFS, 无非就是站在一个node, 知道往左边走还是往右边走; 但是比如题目给的这个例子:
5
/ \
3 6
/ \ \
2 4 7
假如我们这里要找的是11, 那么实际上4和7两个分别在大root 5的左边和右边. 所以说是没有跟传统的BST问题那样, 一条path走完就行了的;
这个是discussion里面一个蛋疼的解法:
The idea is to use binary search method. For each node, we check if k - node->val exists in this BST.
Time Complexity: O(nlogn), Space Complexity: O(h). h is the height of the tree, which is logn at best case, and n at worst case.
public boolean findTarget(TreeNode root, int k) {
return dfs(root, root, k);
}
public boolean dfs(TreeNode root, TreeNode cur, int k){
if(cur == null)return false;
return search(root, cur, k - cur.val) || dfs(root, cur.left, k) || dfs(root, cur.right, k);
}
public boolean search(TreeNode root, TreeNode cur, int value){
if(root == null)return false;
return (root.val == value) && (root != cur)
|| (root.val < value) && search(root.right, cur, value)
|| (root.val > value) && search(root.left, cur, value);
}
基本就是一个逐个搜索的方法. 最后时间不太好, 唯一的优点要么也就是space比较小了; 注意这里他的dfs这个函数的写法, 有两个node参数, arg2是给dfs函数自己用的, 而arg1的这个root, 其实是给search函数用的; 这个自己对两个recursion函数分别看一下参数变化就知道了;
除开这些好像也没有什么其他的解法了;
TODO: 以后看看有没有新的冒出来的好的解法;
Problem Description
Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
Output: True
Example 2:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
Output: False
Difficulty:Easy
Total Accepted:2.3K
Total Submissions:4.4K
Contributor: aghanta
Companies
facebook samsung
Related Topics
tree
Similar Questions
Two Sum Two Sum II - Input array is sorted Two Sum III - Data structure design