二叉树的路径总和问题（递归遍历，回溯算法）

112. 路径总和 - 力扣（LeetCode）

class Solution {
private:    bool traversal(TreeNode*cur,int count){if(!cur->left&&!cur->right&&count==0){return true;}if(!cur->left&&!cur->right){return false;}if(cur->left){count-=cur->left->val;if(traversal(cur->left,count)){return true;}count+=cur->left->val;}if(cur->right){count-=cur->right->val;if(traversal(cur->right,count)){return true;}count+=cur->right->val;}return false;}
public:bool hasPathSum(TreeNode* root, int targetSum) {if(root==NULL){return false;}return traversal(root,targetSum-root->val);}
};

 这道题要寻找是否有一个从根节点到叶子节点的路径的和与目标值相等，我们可以采用遍历二叉树来依次减掉所有的值来判断最后是否为0。

递归的终止条件：如果遇到叶子节点（节点的左右子树都为空），而且count值减到0，则返回true,反之，则返回false。

递归逻辑：在遍历到一个节点时，如果节点的左节点不为空，递归循环这个函数，如果函数的返回值为true,则说明在这条路径上是符合要求的。如果右节点不为空，与左节点的处理方式相同。但在每次左右节点的判断之后，都要将减掉的值加回来，这样才能让count的值回溯回去，去遍历新路径的和。

如果以上所有条件都不满足，则之间返回false。