653. Two Sum IV - Input is a BST

  • 50.8%

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/description/

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.

1
2
3
4
5
6
7
8
9
Example 1:
Input:
5
/ \
3 6
/ \ \
2 4 7

Target = 9
1
2
3
4
5
6
7
8
9
10
11
12
Output: True
Example 2:
Input:
5
/ \
3 6
/ \ \
2 4 7

Target = 28

Output: False

Three simple methods - choose one you like

方法一:

随便一种遍历,然后边边遍历,边放入set,边检查是否能返回。

Method 1.

This method also works for those who are not BSTs. The idea is to use a hashtable to save the values of the nodes in the BST. Each time when we insert the value of a new node into the hashtable, we check if the hashtable contains k - node.val.

Time Complexity: O(n), Space Complexity: O(n).

C++ version:

1
2
3
4
5
6
7
8
9
10
11
bool findTarget(TreeNode* root, int k) {
unordered_set<int> set;
return dfs(root, set, k);
}

bool dfs(TreeNode* root, unordered_set<int>& set, int k){
if(root == NULL)return false;
if(set.count(k - root->val))return true;
set.insert(root->val);
return dfs(root->left, set, k) || dfs(root->right, set, k);
}

方法二:

二叉搜索树,中序遍历应该最好想到

中序遍历后是有序的。

Method 2.

The idea is to use a sorted array to save the values of the nodes in the BST by using an inorder traversal. Then, we use two pointers which begins from the start and end of the array to find if there is a sum k.

Time Complexity: O(n), Space Complexity: O(n).

C++ version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool findTarget(TreeNode* root, int k) {
vector<int> nums;
inorder(root, nums);
for(int i = 0, j = nums.size()-1; i<j;){
if(nums[i] + nums[j] == k)return true;
(nums[i] + nums[j] < k)? i++ : j--;
}
return false;
}

void inorder(TreeNode* root, vector<int>& nums){
if(root == NULL)return;
inorder(root->left, nums);
nums.push_back(root->val);
inorder(root->right, nums);
}

我的代码实现:

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(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
vector<int> nums;
inorder(root, nums);
int left = 0, right = nums.size()-1;
while(left<right){
int sum = nums[left] + nums[right];
if(sum==k)
return true;
else if(sum>k)
right--;
else
left++;
}
return false;
}

void inorder(TreeNode* root, vector<int>& nums){
if(!root) return;
inorder(root->left, nums);
nums.push_back(root->val);
inorder(root->right, nums);
return;
}
};

方法三:

针对每一个点,查找k-node.val是否在BST中

Method 3.

The idea is to use binary search method. For each node, we check if k - node.val exists in this BST.

Time Complexity: O(nlogn), Space Complexity: O(h). h is the height of the tree, which is logn at best case, and n at worst case.

C++ version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool findTarget(TreeNode* root, int k) {
return dfs(root, root, k);
}

bool dfs(TreeNode* root, TreeNode* cur, int k){
if(cur == NULL)return false;
return search(root, cur, k - cur->val) || dfs(root, cur->left, k) || dfs(root, cur->right, k);
}

bool search(TreeNode* root, TreeNode *cur, int value){
if(root == NULL)return false;
return (root->val == value) && (root != cur)
|| (root->val < value) && search(root->right, cur, value)
|| (root->val > value) && search(root->left, cur, value);
}

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

谢谢你,可爱的朋友。