Problem
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
Input: [5, 3, 6, 2, 4, null, 7]
Target = 9
Output: True
My Solutions
迭代二叉树，经每一结点时，存储节点数据于数组中，并将节点数据与数组中的数据进行匹配。
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
vector<int> nums;
stack<TreeNode*> nodeStack;
TreeNode* current = root;
while (current != NULL || !nodeStack.empty()){
while (current != NULL){
//visit the node
if (isExistTarget(nums, current->val, k)) return true;
nums.push_back(current->val);
nodeStack.push(current);
current = current->left;
}
if (!nodeStack.empty()){
current = nodeStack.top();
nodeStack.pop();
current = current->right;
}
}
return false;
}
private:
bool isExistTarget(vector<int>& nums, int nodeVal, int k){
for (int i = 0; i < nums.size(); i++){
if (nums[i] + nodeVal == k) return true;
}
return false;
}
};
最坏情况比较次数为 (n2+n)/2, 还需要size为n的数组空间辅助计算。（n为树节点数）
时间复杂度为 O(N) = O(n2)
很明显这不是唯一的算法，十分单纯的我看来题解。And...
More Solutions
使用哈希表辅助运算。这个算法的思想与上述算法思想有些类似。只是实现方式不同。
class{
public:
bool findTarget(TreeNode* root, int k) {
unordered_set<int> set;
return dfs(root, set, k);
}
private:
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);
}
};
让我们来看下另一个优雅高效的算法。
class{
public:
bool findTarget(TreeNode* root, int k) {
return dfs(root, root, k);
}
private:
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);
}
};
- 遍历到一个节点，对当前节点进行匹配，同时对节点下的所以节点进行匹配(基于DFS)
- 在DFS过程中，根据二叉搜索树的性质进行剪枝。
- 码者的代码风格着实简洁！
(root->val < value) && search(root->right, cur, value)
- search 函数里的这个逻辑表达式，当root->val > value 时，根据逻辑运算的短路求值原则，不会执行search(root->right, cur, value) ！。
- 时间复杂度 O(nlogn) n为结点数
- 空间复杂度 O(h) h为树的高度
