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

# 112. Path Sum

## [題目來源:] https://leetcode.com/problems/path-sum/

## 題目:

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

**A leaf is a node with no children.**

## 解題思考:
1. bfs求所有到left的路徑，判斷target是否於路徑中
2. 遞迴求解(target-root.val)

## Python( two Solutions ):

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 hasPathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: bool
        """
        #dfs求所有到left的路徑
        self.res=set()
        self.bfs(root,0)
        return True if targetSum in self.res else False
    def bfs(self,root,curSum):
        if not root:
            return 
        if not root.left and not root.right:
            self.res.add(curSum+root.val)
        self.bfs(root.left,curSum+root.val)
        self.bfs(root.right,curSum+root.val)
        
    #法2:
    '''
    def hasPathSum(self, root, targetSum):
        if not root:
            return False
        if not root.left and not root.right:
            return root.val==targetSum
        else:
            return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right,targetSum-root.val)
    '''

root=TreeNode(5)
root.insertLeft(4)
root.insertRight(8)
root.left.insertLeft(11)
root.left.left.insertLeft(7)
root.left.left.insertRight(2)
root.right.insertLeft(13)
root.right.insertRight(4)
root.right.right.insertRight(1)
root.printTree()

result=Solution()
ans=result.hasPathSum(root,targetSum = 22)
print(ans)

## C++ ( two Solutions ):

#include<iostream>
#include<vector>
#include<queue>
#include<set>
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) {}
    TreeNode(int x,TreeNode *left, TreeNode *right): val(x), left(nullptr), right(nullptr) {}
};

void InsertLeft(TreeNode *root, int data){
    TreeNode *tmp=root;
    if (tmp->left!=nullptr)
        InsertLeft(tmp->left,data);
    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);
    TreeNode *new_data = new TreeNode(data);
    tmp->right=new_data;
}

void printTree(TreeNode *root){
    TreeNode *tmp=root;
    vector<int> res;
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()){
        TreeNode *curRoot=que.front(); que.pop();
        res.push_back(curRoot->val);
        if (curRoot->left)
            que.push(curRoot->left);
        if (curRoot->right)
            que.push(curRoot->right);
    }
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

class SolutionBFS{
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root==nullptr)
            return false;
        if (!root->left and !root->right)
            return root->val==targetSum;
        else
            return hasPathSum(root->left,targetSum-root->val) || hasPathSum(root->right,targetSum-root->val);
    }
};

class SolutionDFS {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        set<int> res;
        dfs(root,0,res);
        return (res.find(targetSum)!=res.end()? true : false);
    }
    void dfs(TreeNode* root, int curSum, set<int>& res){
        if (root==nullptr)
            return;
        if (!root->left and !root->right)
            res.insert(curSum+root->val);
        dfs(root->left,curSum+root->val,res);
        dfs(root->right,curSum+root->val,res);
    }
};

int main(){

    TreeNode *root=new TreeNode(5);
    InsertLeft(root,4);
    InsertRight(root,8);
    InsertLeft(root->left,11);
    InsertLeft(root->left->left,7);
    InsertRight(root->left->left,2);
    InsertLeft(root->right,13);
    InsertRight(root->right,4);
    InsertRight(root->right->right,1);
    printTree(root);

    SolutionBFS bfs;
    SolutionDFS dfs;
    int targetSum=22;
    cout<<bfs.hasPathSum(root,targetSum)<<" "<<dfs.hasPathSum(root,targetSum)<<endl;
    return 0;

}