問(wèn)題描述：Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
示例圖
解釋：就是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)中的每一條路徑上的節(jié)點(diǎn)數(shù)相加是否會(huì)等于輸入數(shù)
思路：設(shè)一個(gè)整數(shù)ssm装盯，一條路徑算到最后畸写，如果不行就網(wǎng)上回溯至分支處再算
陷阱：一開(kāi)始我以為都是整數(shù)笛质，所以做了個(gè)判斷if(ssm>sum)則直接退出续徽，
其實(shí)人家負(fù)數(shù)也算在里面的，所以必須每條路徑從頭算到尾
代碼如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// 遞歸+回溯法
class Solution {
bool flag = false;
int ssm = 0;
public:
bool hasPathSum(TreeNode* root, int sum) {
if(root == NULL) return false;
if( flag) return true;
ssm += root->val; // 每測(cè)到一個(gè)節(jié)點(diǎn)唁毒，自增
if(root->left == NULL && root->right == NULL&& ssm == sum){ // 該節(jié)點(diǎn)為葉節(jié)點(diǎn)并且查到該值時(shí)狮鸭，flag = true
flag = true;
return true;
}
if(root->left == NULL && root->right == NULL && ssm != sum){ // 葉節(jié)點(diǎn)但是查不到該值時(shí)饰剥，回溯到上一個(gè)單位
ssm -= root->val;
return false;
}
if(root->left != NULL){
hasPathSum(root->left,sum); // 左遞歸
}
if(root->right != NULL){
hasPathSum(root->right,sum); // 右遞歸
}
ssm -= root->val; // 都不行則一層層往上回溯
return flag;
}
};
