LeetCode 1214. 查找两棵二叉搜索树之和

Categories:

题目描述
思路分析
1. 解法一：哈希集合 + DFS（推荐）
相似题目

题目描述

✅ 1214. 查找两棵二叉搜索树之和

思路分析

解法一：哈希集合 + DFS（推荐）

核心思路：

先遍历第一棵 BST，将所有节点值加入集合。

再遍历第二棵 BST，若存在 target - val 在集合中则返回 true。

利用 BST 仅做遍历，不依赖排序性质也可通过。

复杂度分析：

时间复杂度：O(n + m)，其中 n、m 为两棵树的节点数。

空间复杂度：O(n)，存储第一棵树的值。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        Set<Integer> set = new HashSet<>();
        collect(root1, set);
        return exists(root2, set, target);
    }

    private void collect(TreeNode node, Set<Integer> set) {
        if (node == null) {
            return;
        }
        set.add(node.val);
        collect(node.left, set);
        collect(node.right, set);
    }

    private boolean exists(TreeNode node, Set<Integer> set, int target) {
        if (node == null) {
            return false;
        }
        if (set.contains(target - node.val)) {
            return true;
        }
        return exists(node.left, set, target) || exists(node.right, set, target);
    }
}

func twoSumBSTs(root1 *TreeNode, root2 *TreeNode, target int) bool {
    set := make(map[int]struct{})
    collect(root1, set)
    return exists(root2, set, target)
}

func collect(node *TreeNode, set map[int]struct{}) {
    if node == nil {
        return
    }
    set[node.Val] = struct{}{}
    collect(node.Left, set)
    collect(node.Right, set)
}

func exists(node *TreeNode, set map[int]struct{}, target int) bool {
    if node == nil {
        return false
    }
    if _, ok := set[target-node.Val]; ok {
        return true
    }
    return exists(node.Left, set, target) || exists(node.Right, set, target)
}

相似题目

题目	难度	考察点
653. 两数之和 IV - 输入 BST	简单	哈希集合
167. 两数之和 II - 输入有序数组	中等	双指针
230. 二叉搜索树中第K小的元素	中等	BST 遍历
938. 二叉搜索树的范围和	简单	BST 剪枝
173. 二叉搜索树迭代器	中等	中序遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/87618762