Two Sum Of Binary Tree

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 nums;
        stack 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& 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 set;
        return dfs(root, set, k);
    }
private:
    bool dfs(TreeNode* root, unordered_set& 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 함수에 있는 이 논리 표현식은 루트->val>value일 때 논리 연산의 단락 구치 원칙에 따라 search(root->right,cur,value)를 실행하지 않습니다!

시간 복잡도 O(nlogn)n은 결점수

공간 복잡도 O(h)h는 나무의 높이