package com.example.lettcode.test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Class FindTarget
 * @Description 653 两数之和IV 输入BST
 * 给定一个二叉搜索树和一个目标结果，
 * 如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 * <p>
 * 案例 1:
 * 输入:
 * 5
 * / \
 * 3   6
 * / \   \
 * 2   4   7
 * Target = 9
 * 输出: True
 * <p>
 * 案例 2:
 * 输入:
 * 5
 * / \
 * 3   6
 * / \   \
 * 2   4   7
 * Target = 28
 * 输出: False
 * @Author
 * @Date 2020/7/20
 **/
public class FindTarget {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}

/**
 * 解法1: 先中序得到一个非递减的序列，然后再判断
 */
public static boolean findTarget(TreeNode root, int k) {
	boolean flag = false;
	List<Integer> integerList = new ArrayList<>();
	inOrder(root, integerList);
	int p = 0, q = integerList.size() - 1;
	while (p < q) {
		int tmp = integerList.get(p) + integerList.get(q);
		if (tmp == k) return true;
		if (tmp > k) q--;
		else if (tmp < k) p++;
	}
	return false;
}

public static void inOrder(TreeNode root, List<Integer> integerList) {
	if (root == null) return;
	inOrder(root.left, integerList);
	integerList.add(root.val);
	inOrder(root.right, integerList);
}

/**
 *  解法2：利用HashSet 保存已经遍历到的元素，判断是否存在与当前元素之和为目标值的元素
 *  存在即返回false,否则加入到set中并遍历左右子树
 *  使用类静态变量时每一个测试用例执行结束需要清除，否则会重复保存之前的记录
 *  或者使用类成员变量
 */
static Set<Integer> integerSet = new HashSet<>();

public static boolean findTarget(TreeNode root, int k) {
	if (root == null) return false;
	int tmp = k - root.val;
	if (integerSet.contains(tmp)) return true;
	integerSet.add(root.val);
	return findTarget(root.left, k) || findTarget(root.right, k);
}

// 测试用例
public static void main(String[] args) {
	TreeNode root = new TreeNode(5);
	TreeNode treeNode02 = new TreeNode(3);
	TreeNode treeNode03 = new TreeNode(6);
	root.left = treeNode02;
	root.right = treeNode03;
	TreeNode treeNode04 = new TreeNode(2);
	TreeNode treeNode05 = new TreeNode(4);
	treeNode02.left = treeNode04;
	treeNode02.right = treeNode05;
	TreeNode treeNode06 = new TreeNode(7);
	treeNode05.right = treeNode06;
	int target = 9;
	boolean ans = findTarget(root, target);
	integerSet.clear();
	System.out.println("FindTarget demo01 result:" + ans);

	target = 28;
	ans = findTarget(root, target);
	integerSet.clear();
	System.out.println("FindTarget demo02 result:" + ans);

	root = new TreeNode(1);
	target = 2;
	ans = findTarget(root, target);
	integerSet.clear();
	System.out.println("FindTarget demo03 result:" + ans);
}