【两数之和 IV - 输入 BST(653-java)】

两数之和 IV - 输入 BST(653-java)

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

示例 1：

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true

public class LC260_653_findTarget {
    //二叉树
    static List<Integer> tmp = new ArrayList<>();

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

    private static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        tmp.add(root.val);
        dfs(root.right);
    }

    public static void main(String[] args) {
        boolean target = findTarget(TreeNode.createTree(), 3);
        System.out.println(target);
    }
}