LeetCode 653. 两数之和 IV - 输入二叉搜索树

Categories:

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

题目描述

✅ 653. 两数之和 IV - 输入二叉搜索树

思路分析

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

核心思路：

DFS 遍历 BST，同时维护已访问值的集合。

若当前值的补数已存在，直接返回 true。

否则继续遍历。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(n)，用于哈希集合与递归栈。

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

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> seen = new HashSet<>();
        return dfs(root, k, seen);
    }

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

func findTarget(root *TreeNode, k int) bool {
	seen := make(map[int]struct{})
	var dfs func(node *TreeNode) bool
	dfs = func(node *TreeNode) bool {
		if node == nil {
			return false
		}
		if _, ok := seen[k-node.Val]; ok {
			return true
		}
		seen[node.Val] = struct{}{}
		return dfs(node.Left) || dfs(node.Right)
	}

	return dfs(root)
}

相似题目

题目	难度	考察点
1. 两数之和	简单	哈希
167. 两数之和 II - 输入有序数组	简单	双指针
653. 两数之和 IV - 输入二叉搜索树	简单	BST
1214. 查找两棵二叉搜索树之和	中等	BST
560. 和为 K 的子数组	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/85520939