[437] Path Sum III（TBD？）

覺得開始超過我的能力範圍了哈哈哈哈哈（奔入雨中）

原來用一個兩層的recursive 可以解這題！這個應該就算是暴力解（吧）

但似～～～～會overflow，所以把sum 改成long long 之彷彿偷吃步

//void dfs(struct TreeNode* root, int sum, int *count)

void dfs(struct TreeNode* root, long long sum, int *count)

{

if (root ==NULL)

return ;

if (root->val ==sum)

{

(*count)++;

}

dfs(root->left, sum - root->val, count);

dfs(root->right, sum - root->val, count);

}

int pathSum(struct TreeNode* root, int targetSum) {

int ans=0;

if (root!= NULL)

{

dfs(root, targetSum, &ans);

ans += pathSum(root->left, targetSum);

ans += pathSum(root->right, targetSum);

}

return ans;

}

看到有人說可以這樣解： (如果不把它改成long long 的話)

if(root->val % 1000000007 == sum % 1000000007)

(*count)++;

dfs(root->left,(sum-root->val)%1000000007, count);

dfs(root->right,(sum-root->val)%1000000007, count);

一層的雙 recursive 好像比較慢，拆成兩層似乎比較快

void dfs(struct TreeNode* root, long long sum, int *count)

{

if (root ==NULL)

return ;

if (root->val ==sum)

{

(*count)++;

}

dfs(root->left, sum - root->val, count);

dfs(root->right, sum - root->val, count);

}

int outer(struct TreeNode* root, int targetSum) {

int ans=0;

if (root!= NULL)

{

dfs(root, targetSum, &ans);

ans += outer(root->left, targetSum);

ans += outer(root->right, targetSum);

}

return ans;

}

int pathSum(struct TreeNode* root, int targetSum) {

return outer(root, targetSum);

}

又然後XD 聽說可以用hash table 去加速它（是嗎）

我猜是沿路記錄目前的sum吧 然後往下又要把頭減掉（？！）

又有人說是用prefix sum 可以解，我腦細胞已史