[LeetCode]Two Sum IV – Input is a BST

题目描述:


LeetCode 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

题目大意:

给定二叉搜索树BST与一个目标数target,判断BST中是否存在两个数之和等于target。

解题思路:

解法I 递归遍历BST + 利用BST性质进行检索

时间复杂度O(M * H), M是树中节点个数,H是树的深度

Python代码:

# 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
        """
        self.root = root
        self.k = k
        return self.findNumber(root)
    def findNumber(self, root):
        if not root: return False
        node = self.root
        n = self.k - root.val
        if n != root.val:
            while node:
                if node.val == n: return True
                if n > node.val: node = node.right
                else: node = node.left
        return self.findNumber(root.left) or self.findNumber(root.right)

解法II 递归遍历BST + Two Sum

时间复杂度O(M),空间复杂度O(M);M是树中节点个数

Python代码:

# 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
        """
        self.dset = set()
        self.traverse(root)
        for n in self.dset:
            if k - n != n and k - n in self.dset:
                return True
        return False
    def traverse(self, root):
        if not root: return
        self.dset.add(root.val)
        self.traverse(root.left)
        self.traverse(root.right)
书影责编内容来自:书影 (源链) | 更多关于

阅读提示:酷辣虫无法对本内容的真实性提供任何保证,请自行验证并承担相关的风险与后果!
本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合技术 » [LeetCode]Two Sum IV – Input is a BST

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录