首页 > itarticle > algorithm notes: leetcode#653 two sum iv

algorithm notes: leetcode#653 two sum iv

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

class :
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        hash_set = set()
        queue = [root]
        while queue:
            node = queue.pop(0)
            if k - node.val in hash_set:
                return True
            hash_set.add(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return False

Java implementation

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class  {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> hashSet = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while(!queue.isEmpty()){
            TreeNode node = queue.remove();
            if(hashSet.contains(k - node.val))
                return true;
            hashSet.add(node.val);
            if(node.left != null)
                queue.add(node.left);
            if(node.right != null)
                queue.add(node.right);
        }
        return false;
    }
}

Time complexity

O(n).

Space complexity

O(n).

Links

653. Two Sum IV - Input is a BST
(中文版) 算法笔记: 力扣#653 两数之和 IV - 输入 BST