Easy

题目描述

给定二叉搜索树的根节点 root 和一个整数 k，如果二叉搜索树中存在两个元素使得它们的和等于给定的目标值 k，则返回 true，否则返回 false。

示例 1：

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true

示例 2：

输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

提示：

  • 二叉树的节点个数的范围是 [1, 10^4]
  • -10^4 <= Node.val <= 10^4
  • 题目数据保证输入的是一个有效的二叉搜索树
  • -10^5 <= k <= 10^5

解题思路

这道题目有多种解法思路：

方法一：哈希表 + DFS（推荐） 最直观的思路是遍历二叉搜索树，对于每个节点值 val，查看是否存在 k - val。使用哈希表存储已访问的节点值，可以在 O(1) 时间内完成查找。通过 DFS 遍历整棵树，时间复杂度为 O(n)。

方法二：中序遍历 + 双指针 利用二叉搜索树的性质，中序遍历可以得到有序数组。然后在有序数组中使用双指针技巧寻找两数之和。这种方法需要额外的 O(n) 空间存储数组。

方法三：双指针 + 迭代器 更进阶的做法是实现 BST 的前向和后向迭代器，不需要额外存储整个数组，空间复杂度可以优化到 O(h)，其中 h 是树的高度。

方法四：递归搜索 对于每个节点，在 BST 中搜索 k - node.val，但这种方法时间复杂度较高，为 O(n log n)。

考虑到实现简洁性和效率，推荐使用方法一。

代码实现

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> seen;
        return dfs(root, k, seen);
    }
    
private:
    bool dfs(TreeNode* node, int k, unordered_set<int>& seen) {
        if (!node) return false;
        
        int complement = k - node->val;
        if (seen.count(complement)) return true;
        
        seen.insert(node->val);
        
        return dfs(node->left, k, seen) || dfs(node->right, k, seen);
    }
};

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        seen = set()
        
        def dfs(node):
            if not node:
                return False
            
            complement = k - node.val
            if complement in seen:
                return True
            
            seen.add(node.val)
            
            return dfs(node.left) or dfs(node.right)
        
        return dfs(root)

public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        HashSet<int> seen = new HashSet<int>();
        return DFS(root, k, seen);
    }
    
    private bool DFS(TreeNode node, int k, HashSet<int> seen) {
        if (node == null) return false;
        
        int complement = k - node.val;
        if (seen.Contains(complement)) return true;
        
        seen.Add(node.val);
        
        return DFS(node.left, k, seen) || DFS(node.right, k, seen);
    }
}

var findTarget = function(root, k) {
    const seen = new Set();
    
    function dfs(node) {
        if (!node) return false;
        
        const complement = k - node.val;
        if (seen.has(complement)) return true;
        
        seen.add(node.val);
        
        return dfs(node.left) || dfs(node.right);
    }
    
    return dfs(root);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
哈希表 + DFSO(n)O(n)
中序遍历 + 双指针O(n)O(n)
双指针 + 迭代器O(n)O(h)
递归搜索O(n log n)O(h)

其中 n 为树中节点数量，h 为树的高度。推荐解法的时间复杂度为 O(n)，空间复杂度为 O(n)。

相关题目