Question

Formatted question description: https://leetcode.ca/all/653.html

 653	Two Sum IV - Input is a BST

 Given a Binary Search Tree and a target number,
 return true if there exist two elements in the BST such that their sum is equal to the given target.

 Example 1:

 Input:
     5
    / \
   3   6
  / \   \
 2   4   7

 Target = 9

 Output: True


 Example 2:

 Input:
    5
   / \
  3   6
 / \   \
2   4   7

 Target = 28

 Output: False

Algorithm

As long as it is the question of the sum of two numbers, you must remember to try to do it with HashSet.

This question is just to turn the array into a binary tree. We need to traverse the binary tree and use a HashSet. In the recursive function function,

if node is empty, return false.
If k minus the current node value exists in the HashSet, return true directly;
otherwise, add the current node value to the HashSet, and then call the recursive function on the left and right sub-nodes and return together.

Code

Java

public class Two_Sum_IV_Input_is_a_BST {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */

    // https://leetcode.com/problems/two-sum-iv-input-is-a-bst/solution/
    public class Solution_queue {
        public boolean findTarget(TreeNode root, int k) {
            Set<Integer> set = new HashSet<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                if (queue.peek() != null) {
                    TreeNode node = queue.remove();
                    if (set.contains(k - node.val))
                        return true;
                    set.add(node.val);
                    queue.add(node.right);
                    queue.add(node.left);
                } else
                    queue.remove();
            }
            return false;
        }
    }

    // time: O(N)
    // space: O(N)
    public class Solution_usingBST { // inorder traversal to get sorted list
        public boolean findTarget(TreeNode root, int k) {
            List< Integer > list = new ArrayList<>();
            inorder(root, list);
            int l = 0, r = list.size() - 1;
            while (l < r) {
                int sum = list.get(l) + list.get(r);
                if (sum == k)
                    return true;
                if (sum < k)
                    l++;
                else
                    r--;
            }
            return false;
        }
        public void inorder(TreeNode root, List < Integer > list) {
            if (root == null)
                return;
            inorder(root.left, list);
            list.add(root.val);
            inorder(root.right, list);
        }
    }

    // time: O(N)
    // space: O(N)
    public class Solution {
        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);
        }
    }

}

// OJ: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/solution/
// Time: O(NH)
// Space: O(H)
class Solution {
    bool dfs(TreeNode *root, int k, int mn = INT_MIN, int mx = INT_MAX) {
        if (!root || root->val <= mn || root->val >= mx) return false;
        if (root->val == k) return true;
        return root->val < k ? dfs(root->right, k, root->val, mx) : dfs(root->left, k, mn, root->val);
    }
    bool find(TreeNode *root, int k, TreeNode *from) {
        if (!root) return false;
        if (2 * root->val != k && dfs(from, k - root->val)) return true;
        return find(root->left, k, from) || find(root->right, k, from);
    }
public:
    bool findTarget(TreeNode* root, int k) {
        return find(root, k, root);
    }
};

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        if not root: return False
        bfs, s = [root], set()
        for i in bfs:
            print i.val
            if k - i.val in s : return True
            s.add(i.val)
            if i.left : bfs.append(i.left)
            if i.right : bfs.append(i.right)
            print([b.val for b in bfs])
        return False

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Set<Integer> set = new HashSet<Integer>();

    public boolean findTarget(TreeNode root, int k) {
        prePost(root);
        for (int key : set) {
            if (set.contains(k - key) && k - key != key)
                return true;
        }
        return false;
    }

    public void prePost(TreeNode root) {
        if (root == null)
            return;
        set.add(root.val);
        prePost(root.left);
        prePost(root.right);
    }
}

// OJ: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/solution/
// Time: O(NH)
// Space: O(H)
class Solution {
    bool dfs(TreeNode *root, int k, int mn = INT_MIN, int mx = INT_MAX) {
        if (!root || root->val <= mn || root->val >= mx) return false;
        if (root->val == k) return true;
        return root->val < k ? dfs(root->right, k, root->val, mx) : dfs(root->left, k, mn, root->val);
    }
    bool find(TreeNode *root, int k, TreeNode *from) {
        if (!root) return false;
        if (2 * root->val != k && dfs(from, k - root->val)) return true;
        return find(root->left, k, from) || find(root->right, k, from);
    }
public:
    bool findTarget(TreeNode* root, int k) {
        return find(root, k, root);
    }
};

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        if not root: return False
        bfs, s = [root], set()
        for i in bfs:
            print i.val
            if k - i.val in s : return True
            s.add(i.val)
            if i.left : bfs.append(i.left)
            if i.right : bfs.append(i.right)
            print([b.val for b in bfs])
        return False

653 - Two Sum IV - Input is a BST

Question

Algorithm

Code

All Problems

All Solutions