Tree
Depth-First Search
Breadth-First Search
Binary Search Tree
Hash Table
Two Pointers
Binary Tree
Description
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 <= 104
root
is guaranteed to be a valid binary search tree.
-105 <= k <= 105
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def findTarget ( self , root : Optional [ TreeNode ], k : int ) -> bool :
def dfs ( root ):
if root is None :
return False
if k - root . val in vis :
return True
vis . add ( root . val )
return dfs ( root . left ) or dfs ( root . right )
vis = set ()
return dfs ( root )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private Set < Integer > vis = new HashSet <> ();
private int k ;
public boolean findTarget ( TreeNode root , int k ) {
this . k = k ;
return dfs ( root );
}
private boolean dfs ( TreeNode root ) {
if ( root == null ) {
return false ;
}
if ( vis . contains ( k - root . val )) {
return true ;
}
vis . add ( root . val );
return dfs ( root . left ) || dfs ( root . right );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
bool findTarget ( TreeNode * root , int k ) {
unordered_set < int > vis ;
function < bool ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) {
if ( ! root ) {
return false ;
}
if ( vis . count ( k - root -> val )) {
return true ;
}
vis . insert ( root -> val );
return dfs ( root -> left ) || dfs ( root -> right );
};
return dfs ( root );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findTarget ( root * TreeNode , k int ) bool {
vis := map [ int ] bool {}
var dfs func ( * TreeNode ) bool
dfs = func ( root * TreeNode ) bool {
if root == nil {
return false
}
if vis [ k - root . Val ] {
return true
}
vis [ root . Val ] = true
return dfs ( root . Left ) || dfs ( root . Right )
}
return dfs ( root )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function findTarget ( root : TreeNode | null , k : number ) : boolean {
const dfs = ( root : TreeNode | null ) => {
if ( ! root ) {
return false ;
}
if ( vis . has ( k - root . val )) {
return true ;
}
vis . add ( root . val );
return dfs ( root . left ) || dfs ( root . right );
};
const vis = new Set < number > ();
return dfs ( root );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std :: cell :: RefCell ;
use std :: collections ::{ HashSet , VecDeque };
use std :: rc :: Rc ;
impl Solution {
pub fn find_target ( root : Option < Rc < RefCell < TreeNode >>> , k : i32 ) -> bool {
let mut set = HashSet :: new ();
let mut q = VecDeque :: new ();
q . push_back ( root );
while let Some ( node ) = q . pop_front () {
if let Some ( node ) = node {
let mut node = node . as_ref (). borrow_mut ();
if set . contains ( & node . val ) {
return true ;
}
set . insert ( k - node . val );
q . push_back ( node . left . take ());
q . push_back ( node . right . take ());
}
}
false
}
}
Solution 2
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def findTarget ( self , root : Optional [ TreeNode ], k : int ) -> bool :
q = deque ([ root ])
vis = set ()
while q :
for _ in range ( len ( q )):
node = q . popleft ()
if k - node . val in vis :
return True
vis . add ( node . val )
if node . left :
q . append ( node . left )
if node . right :
q . append ( node . right )
return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean findTarget ( TreeNode root , int k ) {
Deque < TreeNode > q = new ArrayDeque <> ();
q . offer ( root );
Set < Integer > vis = new HashSet <> ();
while ( ! q . isEmpty ()) {
for ( int n = q . size (); n > 0 ; -- n ) {
TreeNode node = q . poll ();
if ( vis . contains ( k - node . val )) {
return true ;
}
vis . add ( node . val );
if ( node . left != null ) {
q . offer ( node . left );
}
if ( node . right != null ) {
q . offer ( node . right );
}
}
}
return false ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
bool findTarget ( TreeNode * root , int k ) {
queue < TreeNode *> q {{ root }};
unordered_set < int > vis ;
while ( ! q . empty ()) {
for ( int n = q . size (); n ; -- n ) {
TreeNode * node = q . front ();
q . pop ();
if ( vis . count ( k - node -> val )) {
return true ;
}
vis . insert ( node -> val );
if ( node -> left ) {
q . push ( node -> left );
}
if ( node -> right ) {
q . push ( node -> right );
}
}
}
return false ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findTarget ( root * TreeNode , k int ) bool {
q := [] * TreeNode { root }
vis := map [ int ] bool {}
for len ( q ) > 0 {
for n := len ( q ); n > 0 ; n -- {
node := q [ 0 ]
q = q [ 1 :]
if vis [ k - node . Val ] {
return true
}
vis [ node . Val ] = true
if node . Left != nil {
q = append ( q , node . Left )
}
if node . Right != nil {
q = append ( q , node . Right )
}
}
}
return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function findTarget ( root : TreeNode | null , k : number ) : boolean {
const q = [ root ];
const vis = new Set < number > ();
while ( q . length ) {
for ( let n = q . length ; n ; -- n ) {
const { val , left , right } = q . shift ();
if ( vis . has ( k - val )) {
return true ;
}
vis . add ( val );
left && q . push ( left );
right && q . push ( right );
}
}
return false ;
}