package codeTop;

import java.util.HashSet;

/**
 * Given the roots of two binary tree,root1 and root2,return true if and only if there is a node in the first tree
 * and a node in the second tree whose value sum up to a given integer target
 */
public class LeetCode1214 {

    HashSet<Integer> set = new HashSet<>();

    /**
     * 时间负责度：O(N),空间复杂度：O(n)
     * @param root1
     * @param root2
     * @param target
     * @return
     */
    public boolean twoSumBSTS(TreeNode root1,TreeNode root2,Integer target){
        if(root1 == null || root2 == null){
            return false;
        }
        dfs(root1);
        return process(root2,target);
    }

    //将TreeNode root的所有节点都放到set中
    private void dfs(TreeNode root){
        if(root != null){
            set.add(root.value);
            dfs(root.left);
            dfs(root.right);
        }
    }
    private boolean process(TreeNode root,Integer target){
        if(root == null){
            return false;
        }
        int diff = target - root.value;
        if(set.contains(diff)){
            return true;
        }
        return process(root.left,target) || process(root.right,target);
    }
    /**
     * 方法二：O(nlogn),固定其中一个bst,二分查找另一个。
     *
     */
    public boolean twoSumBSTS2(TreeNode root1,TreeNode root2,Integer target){
        if(root1 == null) return false;
        if(find(root2,target - root1.value)) return true;
        return twoSumBSTS2(root1.left,root2,target) || twoSumBSTS2(root1.right,root2,target);
    }

    private boolean find(TreeNode root,Integer target){
        if(root == null){
            return false;
        }
        if(root.value == target){
            return true;
        }else if(root.value > target){
            return find(root.left,target);
        }else {
            return find(root.right,target);
        }
    }
}

class TreeNode{
    public Integer value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(Integer value){
        this.value = value;
    }
}