路径总和(力扣112)

题目给了我们目标路径和，我们可以每遍历一个节点就让路径和减去该节点的值，如果遍历到该条路径的叶子结点发现路径和刚好减为0，说明我们找到了满足要求的路径。那么我们的递归终止条件自然可以写成遍历到叶子节点，并且遍历到叶子节点就判断路径和是否为0。如果为0，就可以在每一层递归不断返回true，如果不为0，则需要回溯，进而递归其他的路径。但是在代码的编写上我这里给出两种思路，一种是写出父节点的处理逻辑(不知道处理逻辑的含义的，可以看一下我的二叉树遍历的文章)，另外一种是没有处理逻辑，只有左递归和右递归，将路径和减去节点值的操作并入递归中。这就是两种大致的代码思路，大家可以结合下面的代码以及注释理解这道题。

第一种代码及注释如下：

​
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {//由于树是空的，所以不存在根节点到叶子节点的路径if(root == NULL) return false;//终止条件：遍历到叶子结点，直接终止递归if(root != NULL && root -> left == NULL && root -> right == NULL){targetSum -= root -> val;if(targetSum == 0 ) return true;else return false;}//处理逻辑targetSum -= root -> val;//左节点不为空才可以向左递归，否则会影响上面终止条件的判断if(root -> left){if(hasPathSum(root -> left,targetSum) == true) return true;//注意：因为targetSum作为递归函数的参数并没有&，导致调用递归函数实际上只是复制一份变量，并没有真正改变targetSum，所以不需要回溯(这与第二种方法有所区别)}//右节点不为空才可以向右递归if(root -> right){ if(hasPathSum(root -> right,targetSum) == true) return true;}return false;}
};​

第二种代码及注释如下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {//由于树是空的，所以不存在根节点到叶子节点的路径if(root == NULL) return false;//终止条件：遍历到叶子结点，直接终止递归if(root != NULL && root -> left == NULL && root -> right == NULL){targetSum -= root -> val;if(targetSum == 0 ) return true;else return false;}//左节点不为空才可以向左递归，否则会影响上面终止条件的判断if(root -> left){//在总和的基础上减去当前父节点的大小targetSum -= root -> val;//找到了满足条件的路径，就一直返回true到根节点if(hasPathSum(root -> left,targetSum) == true) return true;//未找到满足条件的路径就回溯，加上减去的父节点数值大小targetSum += root -> val;}//右节点不为空才可以向右递归if(root -> right){//在总和的基础上减去当前父节点的大小targetSum -= root -> val;//找到了满足条件的路径，就一直返回true到根节点if(hasPathSum(root -> right,targetSum) == true) return true;//未找到满足条件的路径就回溯，加上减去的父节点数值大小targetSum += root -> val;}return false;}
};