首页 > 代码库 > 653. Two Sum IV - Input is a BST 两个数的和，输入为平衡二叉树

653. Two Sum IV - Input is a BST 两个数的和，输入为平衡二叉树

2024-11-19 17:48:39   203人阅读

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

题意：给定二进制搜索树和目标数字，如果BST中存在两个元素，使得它们的和等于给定目标，则返回true。

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution(object):
  9.     def findTarget(self, root, k):
  10.         """
  11.         :type root: TreeNode
  12.         :type k: int
  13.         :rtype: bool
  14.         """
  15.         if (not root):
  16.             return False
  17.         s = set()
  18.         queue = [root]
  19.         while (queue):
  20.             node = queue.pop(0)
  21.             s.add(node.val)
  22.             if(node.left):
  23.                 queue.append(node.left)
  24.             if(node.right):
  25.                 queue.append(node.right)
  27.         for num in s:
  28.             if k - num in s and 2 * (k - num) != k:
  29.                 return True
  31.         return False



来自为知笔记(Wiz)


653. Two Sum IV - Input is a BST 两个数的和，输入为平衡二叉树


联系
我们