【leetcode】1214.Two Sum BSTs

题目如下：

Given two binary search trees, return True if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

Example 1:
Input: root1 = [2,1,4], root2 = [1,0,3], target = 5

Output: true

Explanation: 2 and 3 sum up to 5.
Example 2:
Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18

Output: false
Note:

Each tree has at most 5000 nodes.

-10^9 <= target, node.val <= 10^9

解题思路：我用的是最直接的方法，把两棵树的节点的值分别存到两个字典中，然后遍历字典，看看能不能组成target。

代码如下：

# 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 twoSumBSTs(self, root1, root2, target):

        """

        :type root1: TreeNode

        :type root2: TreeNode

        :type target: int

        :rtype: bool

        """

        dic1 = {}

        dic2 = {}

        def recursive(node,dic):

            if node != None:

                dic[node.val] = 1

            if node.left != None:

                recursive(node.left,dic)

            if node.right != None:

                recursive(node.right, dic)

        recursive(root1,dic1)

        recursive(root2,dic2)

        for val in dic1.iterkeys():

            if target - val in dic2:

                return True

        return False

巴特西

【leetcode】1214.Two Sum BSTs

最新文章

热门文章