Leetcode 1214:查找两棵二叉搜索树之和(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1214:查找两棵二叉搜索树之和(超详细的解法!!!)

in leetcode with 0 comment

给出两棵二叉搜索树,请你从两棵树中各找出一个节点,使得这两个节点的值之和等于目标值 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

提示:

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

解题思路

首先不难想到暴力法,也就是先通过遍历两颗二叉树得到数组,然后遍历两个数组判断是不是存在和为target的值。树的遍历非常简单,这里使用前序遍历的方式操作,参看这篇Leetcode 144:二叉树的前序遍历(最优雅的解法!!!)

class Solution:
    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:
        def dfs(root, res):
            if root != None:
                res.append(root.val)
                dfs(root.left, res)
                dfs(root.right, res)
            return res 
        
        t1, t2 = [], []
        dfs(root1, t1)
        dfs(root2, t2)
        for i in t1:
            for j in t2:
                if i + j == target:
                    return True
        return False

当然你也可以将其中一个遍历的结果存放在set中,这样我们就不用两重循环了。

class Solution:
    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:
        def dfs(root, res):
            if root != None:
                res.append(root.val)
                dfs(root.left, res)
                dfs(root.right, res)
            return res 
        
        t1, t2 = [], []
        dfs(root1, t1)
        dfs(root2, t2)
        t2 = set(t2)
        for i in t1:
            if target - i in t2:
                return True
        return False

但是这么做的话,题目中的条件两颗树是二叉搜索树我们一直没有使用。实际上我们可以只遍历一颗二叉树,遍历的过程中,假设遍历到的节点是node,判断另一棵树中是不是有target-node.val(查找的时间复杂度是O(logn))。如果有返回True,否则继续遍历,直到遍历完所有节点都没返回True的话,那么就返回False

class Solution:
    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:
        def find(root, t):
            if not root:
                return False
            if root.val == t:
                return True
            elif root.val < t:
                return find(root.right, t)
            else:
                return find(root.left, t)
        
        if not root1:
            return False
        if find(root2, target - root1.val):
            return True
        return self.twoSumBSTs(root1.left, root2, target) or \
            self.twoSumBSTs(root1.right, root2, target)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses