首页 > itarticle > 算法笔记: 力扣#653 两数之和 iv

算法笔记: 力扣#653 两数之和 iv

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

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 实现

 * 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;
    }
}

时间复杂度

O(n).

空间复杂度

O(n).

链接

653. Two Sum IV - Input is a BST
653. 两数之和 IV - 输入 BST
(English version) Algorithm Notes: Leetcode#653 Two Sum IV - Input is a BST