653. 两数之和 IV - 输入 BST

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

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

示例 2：
输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

可以先遍历完毕后根据遍历结果再查找，那么从遍历结果中判断两数之和就类似于 001. 两数之和

public boolean findTarget(TreeNode root, int k) {
    List<Integer> valList = new ArrayList<>();
    order(root,valList);
    return towSum(valList, k);
}
public boolean towSum(List<Integer> valList, int target) {
    for(int i = 0; i < valList.size(); i++) {
        for(int j = 0; j < valList.size(); j++) {
            if (i != j && valList.get(i) + valList.get(j) == target) {
                return true;
            }
        }
    }
    return false;
}
private void order(TreeNode node, List<Integer> valList) {
    if (node == null) {
        return;
    }
    valList.add(node.val);
    order(node.left, valList);
    order(node.right, valList);
}

算法的优化变成了对 towSum 的优化：

public boolean findTarget(TreeNode root, int k) {
    List<Integer> valList = new ArrayList<>();
    order(root,valList);
    return towSum(valList, k);
}
public boolean towSum(List<Integer> valList, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < valList.size(); i++) {
        map.put(valList.get(i), i);
    }
    for(int i = 0; i < valList.size(); i++) {
        int diff = target - valList.get(i);
        if (map.containsKey(diff) && map.get(diff) != i) {
            return true;
        }
    }
    return false;
}
private void order(TreeNode node, List<Integer> valList) {
    if (node == null) {
        return;
    }
    valList.add(node.val);
    order(node.left, valList);
    order(node.right, valList);
}

可以继续优化，减少一次对结果的遍历

public boolean findTarget(TreeNode root, int k) {
    List<Integer> valList = new ArrayList<>();
    order(root,valList);
    return towSum(valList, k);
}
public boolean towSum(List<Integer> valList, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < valList.size(); i++) {
        int diff = target - valList.get(i);
        if (map.containsKey(diff) && map.get(diff) != i) {
            return true;
        }
        map.put(valList.get(i), i);
    }
    return false;
}
private void order(TreeNode node, List<Integer> valList) {
    if (node == null) {
        return;
    }
    valList.add(node.val);
    order(node.left, valList);
    order(node.right, valList);
}

同理可以继续优化，边遍历边比较，无需先遍历一次获取结果

HashMap<Integer, Integer> valMap = new HashMap<>();
boolean isHasTarget = false;
public boolean findTarget(TreeNode root, int k) {
    order(root, k);
    return isHasTarget;
}
private void order(TreeNode node, int k) {
    if (node == null) {
        return;
    }
    // 比较当前值加上已经遍历过的节点中的某一个相加是否等于目标值
    if (valMap.containsKey(k - node.val)) {
        isHasTarget = true;
    }
    // 若没有则继续放入遍历结果集中
    valMap.put(node.val, node.val);
    order(node.left, k);
    order(node.right, k);
}

并且考虑到如果树是二叉搜索树，那么中序遍历可以获取一个升序的有序数组，而对有序数组获取两数之和类似于 167. 两数之和 II - 输入有序数组，有序数组可以利用双指针

public boolean findTarget(TreeNode root, int k) {
    List<Integer> valList = new ArrayList<>();
    order(root,valList);
    return towSum(valList, k);
}
public boolean towSum(List<Integer> valList, int target) {
    int left = 0, right = valList.size() - 1;
    while (left < right) {
        if (valList.get(left) + valList.get(right) == target) {
            return true;
        }
        if (valList.get(left) + valList.get(right) < target) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}
private void order(TreeNode node, List<Integer> valList) {
    if (node == null) {
        return;
    }
    order(node.left, valList);
    valList.add(node.val);
    order(node.right, valList);
}