package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

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

/**
 * 1214. Two Sum BSTs
 *
 * Given two binary search trees,
 * return True if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.
 *
 * Example 1:
 *        2             1
 *       / \           / \
 *      1  4          0  3
 *
 * Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
 * Output: true
 * Explanation: 2 and 3 sum up to 5.
 *
 * Example 2:
 *         0                   5
 *        / \                 / \
 *      -10  10              1   7
 *                          / \
 *                         0  2
 *
 * Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
 * Output: false
 *
 * Constraints:
 * Each tree has at most 5000 nodes.
 * -10^9 <= target, node.val <= 10^9
 * */
public class _1214 {
    public static class Solution1 {
        public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
            if (root1 == null || root2 == null) {
                return false;
            }
            List<Integer> inorder1 = inorderDfs(root1, new ArrayList<>());
            List<Integer> inorder2 = inorderDfs(root2, new ArrayList<>());
            return findTwoSum(inorder1, inorder2, target);
        }

        private boolean findTwoSum(List<Integer> sorted1, List<Integer> sorted2, int target) {
            for (int i = 0; i < sorted1.size(); i++) {
                if (exists(sorted2, target - sorted1.get(i))) {
                    return true;
                }
            }
            return false;
        }

        private boolean exists(List<Integer> sorted, int target) {
            int left = 0;
            int right = sorted.size() - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (sorted.get(mid) == target) {
                    return true;
                } else if (sorted.get(mid) < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return false;
        }

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

    }
}

@@ -134,785 +134,8 @@
 t;%0A%0A
-/**%0A * 1214. Two Sum BSTs%0A *%0A * Given two binary search trees,%0A * return True if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.%0A *%0A * Example 1:%0A *        2             1%0A *       / %5C           / %5C%0A *      1  4          0  3%0A *%0A * Input: root1 = %5B2,1,4%5D, root2 = %5B1,0,3%5D, target = 5%0A * Output: true%0A * Explanation: 2 and 3 sum up to 5.%0A *%0A * Example 2:%0A *         0                   5%0A *        / %5C                 / %5C%0A *      -10  10              1   7%0A *                          / %5C%0A *                         0  2%0A *%0A * Input: root1 = %5B0,-10,10%5D, root2 = %5B5,1,7,0,2%5D, target = 18%0A * Output: false%0A *%0A * Constraints:%0A * Each tree has at most 5000 nodes.%0A * -10%5E9 %3C= target, node.val %3C= 10%5E9%0A * */%0A
 publ

refactor 1214