Algorithm
Problem Name: 653. Two Sum IV - Input is a BST
Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.
Example 1:
Input: root = [5,3,6,2,4,null,7], k = 9 Output: true
Example 2:
Input: root = [5,3,6,2,4,null,7], k = 28 Output: false
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -104 <= Node.val <= 104rootis guaranteed to be a valid binary search tree.-105 <= k <= 105
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
unordered_map<int, int>m;
return DFS(root, m, k);
}
bool DFS(TreeNode* root, unordered_map < int, int>& m, int k){
if(!root) return false;
if(m.count(k - root->val)) return true;
m[root->val]++;
return DFS(root->left, m, k) || DFS(root->right, m, k);
}
};
Input
root = [5,3,6,2,4,null,7], k = 9
Output
true
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean findTarget(TreeNode root, int k) {
if (root == null) {
return false;
}
Stack < TreeNode> stack = new Stack<>();
Set set = new HashSet<>();
while (root != null) {
if (set.contains(k - root.val)) {
return true;
}
stack.push(root);
set.add(root.val);
root = root.left;
}
while (!stack.isEmpty()) {
TreeNode removed = stack.pop();
TreeNode rightNode = removed.right;
while (rightNode != null) {
if (set.contains(k - rightNode.val)) {
return true;
}
stack.push(rightNode);
set.add(rightNode.val);
rightNode = rightNode.left;
}
}
return false;
}
}
Input
root = [5,3,6,2,4,null,7], k = 9
Output
true
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findTarget = function(root, k) {
const m = new Map()
return traverse(root, k, m)
};
function traverse(node, k, m) {
if(node == null) return false
if(m.has(k - node.val)) return true
m.set(node.val, node)
return traverse(node.left,k,m) || traverse(node.right,k,m)
}
Input
root = [5,3,6,2,4,null,7], k = 28
Output
false
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
def traverse(node):
if not node: return False
if not node.val in dic: dic[k-node.val]=1
else: return True
return traverse(node.left) or traverse(node.right)
dic={}
return traverse(root)
Input
root = [5,3,6,2,4,null,7], k = 28
Output
false
#5 Code Example with C# Programming
Code -
C# Programming
//-----------------------------------------------------------------------------
// Runtime: 112ms
// Memory Usage: 30.1 MB
// Link: https://leetcode.com/submissions/detail/342509501/
//-----------------------------------------------------------------------------
using System.Collections.Generic;
namespace LeetCode
{
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class _0653_TwoSumIVInputIsABST
{
public bool FindTarget(TreeNode root, int k)
{
var set = new HashSet < int>();
return InOrder(root, k, set);
}
public bool InOrder(TreeNode node, int k, HashSet < int> set)
{
if (node == null) return false;
if (set.Contains(k - node.val)) return true;
set.Add(node.val);
return InOrder(node.left, k, set) || InOrder(node.right, k, set);
}
}
}
Input
root = [5,3,6,2,4,null,7], k = 9
Output
true