1. 查找两棵二叉搜索树之和-Two Sum BSTs

比较简单的一道题目,和之前的一道两数和非常像

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/two-sum-bsts/

分析

首先给定的二叉搜索树是很好的提示,即两组数据是有序的。

其次还有一点是,所需的两个数字分别位于两个数中,即我们需要从两组数据中得到恰好和为所需值的两个数。

思路一

一个非常简单的方案是,将其中一棵树放入哈希表中,再依次遍历另一颗树,对于每个元素检测其补值(Target - curNum)是否存在哈希表中。

此时时间复杂度为$O(min{|M|, |N|})$。(|M|,|N|分别为两棵树的大小)。

但这个方案需要使用哈希表,显然复杂度的常数较大,并且对空间也有一定的要求。

思路二

使用中序遍历将两棵树的元素分别保存(升序),使用双指针分别指向两个列表的头、尾。

此时可以借鉴文章开头提到的题目思路,不断移动双指针即可。

时间复杂度与空间复杂度均为$O(|M| + |N|)$。(暂未考虑中序遍历时的递归空间需求)

实现

思路一比较简单,思路二的实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

def inorder(node:TreeNode, li:list):
    if node == None:
        return
    inorder(node.left, li)
    li.append(node.val)
    inorder(node.right, li)

class Solution:
    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:
        li_1, li_2 = [], []
        inorder(root1, li_1)
        inorder(root2, li_2)
        p1, p2, len1 = 0, len(li_2) -1, len(li_1)
        
        while p1 < len1 and p2 >=0:
            judge = li_1[p1] + li_2[p2] - target
            if judge == 0:
                return True
            elif judge > 0:
                p2 -= 1
            else:
                p1 += 1
        return False
updatedupdated2021-03-042021-03-04