653. 两数之和 IV

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

案例 1:

输入:
5
/
3 6
/
2 4 7

Target = 9

输出: True

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst

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

public class TwoSumIV653 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            this.val = x;
        }
    }
    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(i < j) {
            int sum = list.get(i) + list.get(j);
            if(sum == k) {
                return true;
            }
            if(sum < k) {
                i++;
            }else {
                j--;
            }
        }
        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);
    }
}