[Swift]LeetCode1214.查找两棵二叉搜索树之和|TwoSumBSTs

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（let_us_code）
➤博主域名：https://www.zengqiang.org
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 = 5
Output: true
Explanation: 2 and 3 sum up to 5.

Example 2:

Input: root1 = 18
Output: false

Note:

Each tree has at most 5000 nodes.
-10^9 <= target, node.val <= 10^9

给出两棵二叉搜索树，请你从两棵树中各找出一个节点，使得这两个节点的值之和等于目标值 Target。

如果可以找到返回 True，否则返回 False。

示例 1：

输入：root1 = [2,1,4], root2 = [1,0,3], target = 5
输出：true
解释：2 加 3 和为 5 。

示例 2：

输入：root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
输出：false

提示：

每棵树上最多有 5000 个节点。
-10^9 <= target, node.val <= 10^9

Runtime: 168 ms

Memory Usage: 23 MB

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func twoSumBSTs(_ root1: TreeNode?, _ root2: TreeNode?, _ target: Int) -> Bool {
16         var s1:Set<Int> = Set<Int>()
17         var s2:Set<Int> = Set<Int>()
18         get(&s1, root1)
19         get(&s2, root2)
20         for i in s1
21         {
22             if s2.contains(target-i) {return true}
23         }
24         return false
25     }
26     
27     func get(_ s:inout Set<Int>,_ root: TreeNode?)
28     {
29         if root != nil
30         {
31             s.insert(root!.val)
32             get(&s, root!.left)
33             get(&s, root!.right)
34         }
35     }
36 }