[LeetCode] Two Sum IV - Input is a BST 两数之和之四 - 输入是二叉搜索树

简介:

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7
Target = 9
Output: True

Example 2:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7
Target = 28
Output: False

这道题又是一道2sum的变种题,博主一直强调,平生不识TwoSum,刷尽LeetCode也枉然!只要是两数之和的题,一定要记得用哈希表来做,这道题只不过是把数组变成了一棵二叉树而已,换汤不换药,我们遍历二叉树就行,然后用一个哈希set,在递归函数函数中,如果node为空,返回false。如果k减去当前结点值在哈希set中存在,直接返回true;否则就将当前结点值加入哈希set,然后对左右子结点分别调用递归函数并且或起来返回即可,参见代码如下:

解法一:

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

我们也可以用层序遍历来做,这样就是迭代的写法了,但是利用哈希表的精髓还是没变的,参见代码如下:

解法二:

public:
    bool findTarget(TreeNode* root, int k) {
        if (!root) return false;
        unordered_set<int> s;
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
          auto t = q.front(); q.pop();
          if (s.count(k - t->val)) return true;
          s.insert(t->val);
          if (t->left) q.push(t->left);
          if (t->right) q.push(t->right);
        }
        return false;
    }
};

参考资料:

https://discuss.leetcode.com/topic/98440/java-c-three-simple-methods-choose-one-you-like

https://discuss.leetcode.com/topic/100110/my-c-non-recursive-solution-using-unordered_set-and-stack

本文转自博客园Grandyang的博客,原文链接:[LeetCode] Two Sum IV - Input is a BST 两数之和之四 - 输入是二叉搜索树

,如需转载请自行联系原博主。

相关文章
|
23天前
【LeetCode 45】701.二叉搜索树中的插入操作
【LeetCode 45】701.二叉搜索树中的插入操作
9 1
|
23天前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
13 1
|
24天前
|
C++
Leetcode第一题(两数之和)
这篇文章介绍了解决LeetCode第一题“两数之和”的两种方法:暴力法和哈希表法,并提供了相应的C++代码实现。
26 0
Leetcode第一题(两数之和)
|
23天前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
34 0
|
23天前
【LeetCode 47】669.修剪二叉搜索树
【LeetCode 47】669.修剪二叉搜索树
8 0
|
23天前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
10 0
|
23天前
【LeetCode 42】501.二叉搜索树中的众数
【LeetCode 42】501.二叉搜索树中的众数
8 0
|
23天前
【LeetCode 41】530.二叉搜索树的最小绝对差
【LeetCode 41】530.二叉搜索树的最小绝对差
9 0
|
23天前
【LeetCode 40】98.验证二叉搜索树
【LeetCode 40】98.验证二叉搜索树
10 0
|
23天前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
12 0