112、路径总和

本文主要是介绍112、路径总和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

代码如下：

class Solution {
public:bool PathSum(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(PathSum(cur->left,count)) return true;count +=cur->left->val;}if(cur->right){count -= cur->right->val;if(PathSum(cur->right,count)) return true;count +=cur->right->val;}        return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(root == NULL) return false;return PathSum(root,targetSum-root->val);}
};

注意：

1、注意回溯是发生在遍历完一个节点后在回溯，而不是在单层递归逻辑中，否则就相当于每次递归什么都没做

2、若采用递减判断，主函数传参传入的是减去了根节点值的目标值

这篇关于112、路径总和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---