LEETCODE 1214. Two Sum BSTs 解题思路分析

题目大意:

查找两棵二叉搜索树之和

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1214

解题思路分析:

这是一道二叉搜索树版本的Two Sum,二叉搜索树的基本特征即是,当前节点的左侧子分支都小于自身,而右侧子分支都大于自身。我们可以遍历一棵树A的所有节点,分别用这些节点去另外一棵树B去寻找和,如果A树与B树当前节点和等于target,返回true,不相同时,进行二分查找:若大于target时,B树的节点移动到其左子节点,小于target时移动到B的右子节点。当B树遍历结束之后仍没找到答案,此时可将A树的当前节点移动到其左子节点或右子节点,然后再在B树中二分查找。

实现代码:

public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
    // 如果root2为空,返回false
    if(root2==null) return false;
    // 利用root2的当前节点去root1中找到和为target的值。
    // 若没找到,继续用root2的左右子节点去找
    return help(root1, root2.val, target)
        || twoSumBSTs(root1, root2.left, target)
        || twoSumBSTs(root1, root2.right, target);
}
boolean help(TreeNode root1, int value, int target){
    // 如果root1为空返回false
    if(root1==null) return false;
    // 计算两棵树当前节点和
    int sum=root1.val+value;
    // 如果sum等于target,返回true
    if(sum==target) return true;
    // 如果sum大于target,减小root1的值
    if(sum>target){
        // 使用root1左子节点的值继续递归
        return help(root1.left,value,target);
    }else{ // 反之
        // 使用root1右子节点的值继续递归
        return help(root1.right,value,target);
    }
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Two Sum BSTs.

Memory Usage: 39.5 MB, less than 100.00% of Java online submissions for Two Sum BSTs.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1214-two-sum-bsts-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。