LeetCode 图解 | 1214.查找两颗二分搜索树之和

点击上方蓝字设为星标LeetCode 图解 | 1214.查找两颗二分搜索树之和

下面开始今天的学习~

LeetCode 图解 | 1214.查找两颗二分搜索树之和


今天分享的题目来源于 LeetCode 第 1214 号问题:查找两颗二分搜索树之和。会员题

题目描述

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

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

示例 1:

LeetCode 图解 | 1214.查找两颗二分搜索树之和


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

示例 2:

LeetCode 图解 | 1214.查找两颗二分搜索树之和


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

提示:

  • 每棵树上最多有 5000 个节点。

  • -10^9 <= target, node.val <= 10^9

题目解析

这道题和第1道题(两数之和)很相似啊,想起我们第一次接触LeetCode的时候,第1道题就这么醒目地排在最前面。

题目越排在前面,就越受到大家的参与。

第1道题的解题思路很简单,使用暴力解决就可以办到,两个for循环解决了。再优化,就需要用到散列表解决,时间复杂度和空间复杂度都可以降低到O(n),比暴力法的时间复杂度O(n^2)要快很多。

回到解题思路,我们也利用上二分搜索树的性质,可以让这道题进行二分法解决。

我们先固定一棵树的一个节点,将目标值 Target 减去这个节点的值,得到新的目标值 target

将这个新的目标值和另外一棵树进行比较,利用二分搜索数的特性进行查找命中,从根节点开始。

  • 如果新的目标值 target 和根节点的值相等,则直接返回 true ;

  • 如果新的目标值比根节点小,进行左递归查找;

  • 如果新的目标值比根节点大,进行右递归;

  • 依次类推,直到树底下的节点为空,才返回 false。

固定一棵树的一个节点,查找另一棵树的节点的时间复杂度是 O(logn)。因为一棵树需要遍历,所以这道题的时间复杂度是 O(nlogn)。

动画理解

参考代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        if (!root1) return false;
        if (find(root2, target - root1.val)) return true;
        return twoSumBSTs(root1.left, root2, target) || 
        twoSumBSTs(root1.right, root2, target);            
    }

    private boolean find(TreeNode node, int target) {
        if (!node) return false;
        if (node.val == target) return true;
        else if (target < node.val) return find(node.left, target);
        else return find(node.right, target);
    }
}

LeetCode 图解 | 1214.查找两颗二分搜索树之和

原文始发于微信公众号(五分钟学算法):LeetCode 图解 | 1214.查找两颗二分搜索树之和

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » LeetCode 图解 | 1214.查找两颗二分搜索树之和

我还会在以下平台发布内容

GitHub 哔哩哔哩