[LeetCode] Problem 653 - Two Sum IV - Input is a BST

Posted on | In ,

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

No.1

Input: 

1
2
3
4
5
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

No.2

Input: 

1
2
3
4
5
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public boolean findTarget(TreeNode root, int k) {
    List<Integer> list = new ArrayList<>();
    inorder(list, root);

    int left = 0;
    int right = list.size() - 1;

    while (left < right) {
        if (list.get(left) + list.get(right) < k)
            left++;
        else if (list.get(left) + list.get(right) > k)
            right--;
        else
            return true;
    }

    return false;
}

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