LeetCode 第 10 次双周赛第 2 题,查找两棵二叉搜索树之和,中等难度。

题目

原题链接

本次双周赛题目已公布,可在赛事主页再次进行虚拟竞赛。虚拟竞赛不计入赛事积分排名。

题目描述

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

解题

AC 样例

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @param {number} target
 * @return {boolean}
 */
var twoSumBSTs = function(root1, root2, target) {
  const hash1 = {}, hash2 = {};
  helper(root1, target, hash1);
  helper(root2, target, hash2);
  
  const arr = Object.values(hash1).filter(num => hash2[num] != null);
  return arr.length? true: false;
};

const helper = (root, target, hash) => {
  if(root) {
    hash[root.val] = target - root.val;
    helper(root.left, target, hash);    
    helper(root.right, target, hash);
  }
}

解题思路

根据题目要求,分别遍历两个二叉树,并检查遍历得到的数据是否符合题目要求。由于涉及到两个树的数据操作,选择使用哈希表存储遍历结果辅助查询,结果记录为目标值与当前值的差,这一纪录对二叉树遍历次序无要求。

两个树的遍历结果分别记为两个哈希表,最后检索两表之间是否存在前表值作为后表键的记录,如存在则两数关系符合题目要求。该解法所需额外空间规模与数据规模一致,所需时间规模与数据规模一致。