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

链接：653.两数之和IV-输入二叉搜索树
难度：Easy
标签：树、深度优先搜索、广度优先搜索、二叉搜索树、哈希表、双指针、二叉树
简介：给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

题解 1 - typescript

• 编辑时间：2021-08-20
• 执行用时：168ms
• 内存消耗：46.8MB
• 编程语言：typescript
• 解法介绍：层序遍历时判断每个值。

function findTarget(root: TreeNode | null, k: number): boolean {
  if (root === null) return false;
  const set = new Set<number>();
  const q = [root];
  while (q.length) {
    const node = q.shift()!;
    if (set.has(node.val)) return true;
    set.add(k - node.val);
    node.left && q.push(node.left);
    node.right && q.push(node.right);
  }
  return false;
}

题解 2 - cpp

• 编辑时间：2022-03-21
• 执行用时：36ms
• 内存消耗：37.7MB
• 编程语言：cpp
• 解法介绍：dfs。

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