[112] Path Sum

某種程度上來說，算是作弊的一題吧Orz

雖然看似是遍歷一遍就可以找到答案的，

但卡在一個很關鍵的地方是我突然不知道要怎麼把sum一個一個加下去檢查！（吶喊臉）

所以我其實不會寫扣是不是Orz

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

bool hasPathSum(struct TreeNode* root, int targetSum){

if (root ==NULL)

return false;

if ((root->left ==NULL)&& (root->right)==NULL && (root->val-targetSum==0) )

return true;

return (hasPathSum(root->left, targetSum-root->val) || hasPathSum(root->right,targetSum-root->val));

}

輕微修改可以變快很多？！

所以我是不是不會寫扣Orz

bool hasPathSum(struct TreeNode* root, int targetSum){

if (root ==NULL)

return false;

if ((root->left ==NULL)&& (root->right==NULL) )

return (targetSum == root->val);

int newSum = targetSum-root->val;

return (hasPathSum(root->left, newSum) || hasPathSum(root->right,newSum));

}