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;
    }
};

 最坏情况比较次数为 (n²+n)/2, 还需要size为n的数组空间辅助计算。（n为树节点数）
 时间复杂度为 O(N) = O(n²)
 很明显这不是唯一的算法，十分单纯的我看来题解。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为树的高度