人森很精彩，所以要把所有事情都記起來=ˇ=

這個題目呢，會給你一個tree和一個目標值

要計算一個tree從root到最底的node一條通道加起來的數值有沒有辦法等於目標值

只要有一條路符合，就會回傳true

舉例來說：

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

目標值為22

這樣就要回傳true，因為5+4+11+2=22

如果目標值為20是不行的，因為5+4+11雖然等於20，但並沒有到最底的node

Sol:

看到這種tree的問題，第一個先想到遞迴

基本上我們可以設想一個function來做這件事情：

bool dfs(TreeNode* node, int sum, const int& target)

node是目前要拜訪的節點，sum是目前加總的值，target是目標值

然後回傳true的條件是：

1. sum + node->val == target

2. node->left == nullptr && node->right == nullptr

這樣想大概可以寫成這樣：

bool dfs(TreeNode* node, int sum, const int& target)

{

        if (node == nullptr)
            return false;
        
        if (node->left == nullptr && node->right == nullptr)
        {
            if (sum + node->val == target)
                return true;
            else
                return false;
        }
        
        sum += node->val;

        return __________;

}

大概完成一半了，那麼紅色底線裡面要填什麼呢

前面說過要用遞迴嘛

左邊子樹和右邊子樹裡面，只要有一個滿足條件就可以回傳true了

所以紅色底線內可以這麼寫：

return dfs(node->left, sum, target) || dfs(node->right, sum, target);

這樣就大功告成了

雖然看起來很簡單，不過一些思考的方式還是值得去記一記的

可以忘記題目，但思考方式要練習啊~~

如果結合上面的想法，也可以簡化成一個非常簡單的方式：

bool hasPathSum(TreeNode *root, int sum) {
        if (root == NULL) return false;
        if (root->val == sum && root->left == NULL && root->right == NULL) return true;
        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
    }

這是leetcode上面網友的解法，是用減法來做的，其實想法差不多

不過code差很多啊XDDD

還是有多進步空間啦~ 加油吧~