Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

 

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Example 3:

Input: root = [2,1,3], k = 4
Output: true

Example 4:

Input: root = [2,1,3], k = 1
Output: false

Example 5:

Input: root = [2,1,3], k = 3
Output: true

方法一：先把bst转化成一个sorted arraylist, 然后用上一题的方法即可。

class Solution {
  public boolean findTarget(TreeNode root, int k) {
    if (root == null) {
      return false;
    }
    List<Integer> list = new ArrayList();
    inorder(root, list);
    int i = 0;
    int j = list.size() - 1;

    while (j > i) {
      long sum = list.get(i) + list.get(j);
      if (sum == k) {
        return true;
      } else if (sum > k) {
        j--;
      } else {
        i++;
      }
    }
    return false;
  }

  private void inorder(TreeNode root, List<Integer> list) {
    if (root == null) {
      return;
    }
    inorder(root.left, list);
    list.add(root.val);
    inorder(root.right, list);
  }
}

方法二：利用递归+ hashset. 这个方法有点意思，所以记录下来。

 1 class Solution {
 2   public boolean findTarget(TreeNode root, int k) {
 3     if (root == null) {
 4       return false;
 5     }
 6     Set<Integer> numbers = new HashSet();
 7     return dfs(root, numbers, k);
 8   }
 9 
10   private boolean dfs(TreeNode root, Set<Integer> numbers, int k) {
11     if (root == null) {
12       return false;
13     }
14 
15     if (numbers.contains(k - root.val)) {
16       return true;
17     }
18     numbers.add(root.val);
19     return dfs(root.left, numbers, k) || dfs(root.right, numbers, k);
20   }
21 }

方法三：利用bst iterator

 1 class Solution {
 2     class BSTIterator {
 3         private Stack<TreeNode> stack;
 4         private boolean isForward = true;
 5 
 6         public BSTIterator(TreeNode root, boolean flag) {
 7             this.isForward = flag;
 8             stack = new Stack<>();
 9             TreeNode node = root;
10             while (node != null) {
11                 stack.push(node);
12                 node = isForward ? node.left : node.right;
13             }
14         }
15 
16         /** @return whether we have a next smallest number */
17         public boolean hasNext() {
18             return !stack.isEmpty();
19         }
20 
21         public int peek() {
22             return stack.peek().val;
23         }
24 
25         /** @return the next smallest number */
26         public int next() {
27             TreeNode node = stack.pop();
28             int val = node.val;
29             node = isForward ? node.right : node.left;
30             while (node != null) {
31                 stack.push(node);
32                 node = isForward ? node.left : node.right;
33             }
34             return val;
35         }
36     }
37 
38     public boolean findTarget(TreeNode root, int k) {
39         BSTIterator left = new BSTIterator(root, true);
40         BSTIterator right = new BSTIterator(root, false);
41         while (left.hasNext() && right.hasNext()) {
42             int l = left.peek(), r = right.peek();
43             if (l >= r)
44                 return false;
45             if (l + r == k)
46                 return true;
47             else if (l + r < k) {
48                 left.next();
49             } else {
50                 right.next();
51             }
52         }
53         return false;
54     }
55 }