###### tags: `Leetcode` `easy` `tree` `hash` `python` `c++`

# 653. Two Sum IV - Input is a BST

## [題目連結:] https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

## 題目:
Given the ```root``` of a Binary Search Tree and a target number ```k```, return ```true``` if there exist two elements in the ```BST``` such that their sum is equal to the given target.

#### [圖片來源] https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

## 解題想法:
* 題目為給一BST，求任兩點val和等於target k
* 使用字典存
* key:root.val
* val:target-root.val
* dfs遍歷所有點，判斷該key之val是否同時為key存在字典中
* 注意，應需在dfs同時，即進行判斷
* **不能dfs跑完紀錄所有組合到dic後，再統一判斷，會error**
* ex: 特殊情況root=[4],k=8, 應該是False
* 因為只有一點 dic[4]=4
* 但同時此val=4也為key，判斷上會出錯

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        #dfs遍歷所有node
        self.dic={} #key:root.val val:target-root.val
        self.res=False
        self.dfs(root,k)
        return self.res
    def dfs(self,root,k):
        if not root:
            return
        if k-root.val in self.dic:
            self.res=True
            return 
        self.dic[root.val]=k-root.val
        self.dfs(root.left,k)
        self.dfs(root.right,k)
                

if __name__=='__main__':
    root=TreeNode(1)
    result=Solution()
    ans=result.findTarget(root,2)
    print(ans) #False

## C++:

#include<iostream>
#include<queue>
#include<vector>
#include<unordered_map>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0), left(nullptr), right(nullptr){}
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

void InsertLeft(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->left!=nullptr)
        InsertLeft(tmp->left,data);
    else{
        TreeNode *new_data= new TreeNode(data);
        tmp->left=new_data;
    }
}

void InsertRight(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->right!=nullptr)
        InsertRight(tmp->right,data);
    else{
        TreeNode *new_data= new TreeNode(data);
        tmp->right=new_data;
    }
}

void PrintTree(TreeNode *root){
    TreeNode *tmp=root;
    queue<TreeNode*> que;
    vector<int> res;
    que.push(root);
    while (!que.empty()){
        TreeNode *root=que.front(); que.pop();
        res.push_back(root->val);
        if (root->left)
            que.push(root->left);
        if (root->right)
            que.push(root->right);
    }
    for (auto val: res){
        cout<<val<<" ";
    }
    cout<<endl;
}

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        unordered_map<int,int> dic;
        dfs(root, k, dic);
        return res;
    }
    void dfs(TreeNode*root, int k, unordered_map<int,int>& dic){
        if (root==nullptr)
            return ;
        //find
        if (dic.find(k-root->val)!=dic.end()){
            res=true;
            return ;
        }
        else
            dic[root->val]=k-root->val;
        dfs(root->left, k, dic);
        dfs(root->right, k ,dic);
    }
private:
    bool res=false;
};

int main(){
    TreeNode *root=new TreeNode(5);
    InsertLeft(root,3);
    InsertRight(root,6);
    InsertLeft(root->left,2);
    InsertRight(root->left,4);
    InsertRight(root->right,7);

    Solution res;
    bool ans=res.findTarget(root,9);
    cout<<ans<<endl;
    return 0;
}