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

?迭代二叉樹，經(jīng)每一結(jié)點(diǎn)時，存儲節(jié)點(diǎn)數(shù)據(jù)于數(shù)組中，并將節(jié)點(diǎn)數(shù)據(jù)與數(shù)組中的數(shù)據(jù)進(jìn)行匹配。

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

?最壞情況比較次數(shù)為 (n²+n)/2, 還需要size為n的數(shù)組空間輔助計(jì)算。（n為樹節(jié)點(diǎn)數(shù)）
?時間復(fù)雜度為 O(N) = O(n²)
?很明顯這不是唯一的算法，十分單純的我看來題解。And...

More Solutions

?使用哈希表輔助運(yùn)算。這個算法的思想與上述算法思想有些類似。只是實(shí)現(xiàn)方式不同。

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

?讓我們來看下另一個優(yōu)雅高效的算法。

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

• 遍歷到一個節(jié)點(diǎn)，對當(dāng)前節(jié)點(diǎn)進(jìn)行匹配，同時對節(jié)點(diǎn)下的所以節(jié)點(diǎn)進(jìn)行匹配(基于DFS)
• 在DFS過程中，根據(jù)二叉搜索樹的性質(zhì)進(jìn)行剪枝。
• 碼者的代碼風(fēng)格著實(shí)簡潔！

(root->val < value) && search(root->right, cur, value) 

• search 函數(shù)里的這個邏輯表達(dá)式，當(dāng)root->val > value 時，根據(jù)邏輯運(yùn)算的短路求值原則，不會執(zhí)行search(root->right, cur, value) ！。
• 時間復(fù)雜度 O(nlogn) n為結(jié)點(diǎn)數(shù)
• 空間復(fù)雜度 O(h) h為樹的高度