查找两棵二叉搜索树之和

难度: Medium

Submission

运行时间: 49 ms

内存: 19.6 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
        d = set()
        def dfs(node, verify):
            if not node:
                return False
            if verify and node.val in d:
                return True
            d.add(target-node.val)
            return dfs(node.left, verify) or dfs(node.right, verify)
        dfs(root1, False)
        return dfs(root2, True)

Explain

该题解采用了一种混合的深度优先搜索（DFS）和哈希表的方法来解决问题。首先，通过对第一棵二叉搜索树进行DFS遍历，将每个节点的补数（即 target 减去该节点的值）存储在一个哈希表中。然后，对第二棵树进行DFS遍历，查看每个节点的值是否已经存在于哈希表中。如果存在，说明存在两个节点的值加和为 target，返回 True。否则，继续搜索直到遍历完整棵树。

时间复杂度: O(n + m)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         this.val = val
#         this.left = left
#         this.right = right
class Solution:
    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
        d = set() # 创建一个集合用来存储第一棵树的节点补数
        def dfs(node, verify):
            if not node:
                return False
            if verify and node.val in d: # 如果是验证阶段并且节点值在集合中，找到一对
                return True
            d.add(target-node.val) # 否则将当前节点值的补数添加到集合中
            return dfs(node.left, verify) or dfs(node.right, verify) # 继续递归左右子树
        dfs(root1, False) # 先对第一棵树进行填充集合的遍历
        return dfs(root2, True) # 再对第二棵树进行验证的遍历

Explore

在这种方法中，实际上我们并不能保证哈希表中存储的补数不会与第二棵树的非目标节点的值发生冲突。这是因为哈希表存储的是从第一棵树中计算出的所有可能与目标值相加得到target的补数。如果第二棵树中存在一个值，它恰好也是某个非目标节点的值但与target的另一个补数相等，这种情况在理论上是可能的。但这种情况在实际应用中相对少见，尤其是当节点值分布较为均匀时。此外，目标是找到是否存在至少一对满足条件的节点对，一旦找到这样的对，算法就会停止，因此即使有冲突，也不会影响结果的正确性。

选择哪棵树先进行补数存储取决于树的结构和大小。通常，选择较小或结构较为简单的树进行补数存储是更有效的，因为这将减少哈希表中的条目数量，从而优化查找速度。如果调换顺序，对于大多数情况，算法的效率和最终结果不会受到影响。然而，如果一棵树显著大于另一棵，将较小的树用于构建哈希表会更优，因为这样可以减少内存使用和潜在的查找时间。

理论上，一旦在第二棵树中找到一个节点的值在哈希表中匹配成功，就意味着已经找到了一个符合条件的节点对，可以立即返回True，因此不需要继续遍历该节点的子树。然而，如果问题需要找到所有满足条件的节点对，则需要继续遍历。在本题中，我们只需要找到至少一对符合条件的节点，因此找到匹配后即可停止进一步搜索。

在哈希表中存储补数而不是节点的原始值主要是为了直接与第二棵树节点的值进行比较，这样可以快速检查是否存在两个值的和等于目标值。这种方法可以显著提高查找速度，因为它允许算法在遍历第二棵树时直接检查当前节点值是否已在哈希表中，从而即刻确定是否找到了匹配的节点对，避免了额外的计算或查找步骤。