LeetCode88|两数之和IV-输入BST

案例 1:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True
 

案例 2:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

输出: False

 

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

public class FindTargetTest {
    private static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(5);
        TreeNode t2 = new TreeNode(3);
        TreeNode t3 = new TreeNode(6);
        TreeNode t4 = new TreeNode(2);
        TreeNode t5 = new TreeNode(4);
        TreeNode t6 = new TreeNode(7);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        t3.right = t6;
        int k = 9;
        boolean target = findTarget(t1, k);
        System.out.println("target = " + target);

    }

    public static boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        inOrder(root);
        int i = 0;
        int j = list.size() - 1;
        while (i < j) {
            Integer left = list.get(i);
            Integer right = list.get(j);
            if (left + right == k) {
                return true;
            } else if (left + right > k) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }

    private static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            inOrder(root.left);
        }
        list.add(root.val);
        if (root.right != null) {
            inOrder(root.right);
        }
    }
}