Zenefits: 2Sum in BST
Input: A binary search tree, consisting of integers. And a number k
Output: True if there are two nodes a and b in the tree, such that a.val + b.val = k.
Return false otherwise.
A O(n) time, O(n) space solution:
The most straight-forward solution is first do a in-order traverse of the BST, store the results into an array. Then the problem can be transformed into a 2 sum problem.
So the time and space complexity for this solution is O(n).
A O(n) time, O(log n) space solution:
Output: True if there are two nodes a and b in the tree, such that a.val + b.val = k.
Return false otherwise.
A O(n) time, O(n) space solution:
The most straight-forward solution is first do a in-order traverse of the BST, store the results into an array. Then the problem can be transformed into a 2 sum problem.
So the time and space complexity for this solution is O(n).
A O(n) time, O(log n) space solution:
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| import java.util.*;public class Solution { public boolean twoSumBST(TreeNode root, int k) { if (root == null) { return false; } Stack<TreeNode> leftStack = new Stack<>(); Stack<TreeNode> rightStack = new Stack<>(); TreeNode p = root; while (p != null) { leftStack.push(p); p = p.left; } p = root; while (p != null) { rightStack.push(p); p = p.right; } p = leftStack.peek(); TreeNode q = rightStack.peek(); while (p.val < q.val && p != q) { if (p.val + q.val == k) { return true; } else if (p.val + q.val < k) { leftStack.pop(); if (p.right != null) { p = p.right; while (p != null) { leftStack.push(p); p = p.left; } } if (leftStack.isEmpty()) { return false; } p = leftStack.peek(); } else if (p.val + q.val > k) { rightStack.pop(); if (q.left != null) { q = q.left; while (q != null) { rightStack.push(q); q = q.right; } } if (rightStack.isEmpty()) { return false; } q = rightStack.peek(); } } return false; } public static void main(String[] args) { Solution solution = new Solution(); TreeNode root = new TreeNode(4); root.left = new TreeNode(2); root.right = new TreeNode(6); root.left.left = new TreeNode(1); root.left.right = new TreeNode(3); root.right.left = new TreeNode(5); root.right.right = new TreeNode(8); boolean result = solution.twoSumBST(root, 3); System.out.println(result); }}class TreeNode { int val; TreeNode left, right; public TreeNode(int val) { this.val = val; left = null; right = null; }} |
Thank you very much. It's awesome.
ReplyDelete