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

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

题目描述

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

题目解析

这道题和第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);
    }
}