LeetCode 653. Two Sum IV - Input is a BST

Problem

LeetCode 653. Two Sum IV - Input is a BST

1. 题目简述

给出一棵BST树，以及一个目标数k，判断bst树里是否存在两个node使得其value和为k。

Example: 

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

2. 算法思路

这题和two sum其实是基本一致的，而且可以利用bst树的性质，中序遍历是有序的。但是其实没必要用，直接DFS或者BFS都行，依然利用hashset来查找。

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
    // 其实这题的核心点在于“two numbers”，也就是说，无论是BFS还是DFS遍历，假设存在a和b两个数字符合要求，那么无论先遍历到a还是b都无所谓，通过hashset来完成查找。
    public boolean findTarget(TreeNode root, int k) {
        Set < Integer > set = new HashSet();
        return find(root, k, set);
    }
    public boolean find(TreeNode root, int k, Set < Integer > set) {
        if (root == null)
            return false;
        if (set.contains(k - root.val))
            return true;
        set.add(root.val);
        return find(root.left, k, set) || find(root.right, k, set);
    }
}