java-solutions/src/main/java/leetcode/TwoSumIV.java at master · nikoo28/java-solutions · GitHub

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package leetcode;

import util.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author nikoo28 on 9/17/17
 */
class TwoSumIV {

  public boolean findTarget(TreeNode root, int k) {

    List<Integer> elements = new ArrayList<>();
    inorder(root, elements);

    for (int i = 0, j = elements.size()-1; i <j ; ) {

      if (elements.get(i) + elements.get(j) == k)
        return true;

      if (elements.get(i) + elements.get(j) > k)
        j--;
      else
        i++;
    }

    return false;

  }

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

}