题解 | #二叉树中和为某一值的路径(一)#
二叉树中和为某一值的路径(一)
http://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c
递归+回溯
思路： 与大部分解法一样，考虑用前序遍历，遍历任意一条路径到叶子节点并记录路径上的和，如果此时和与目标结果相等则找到满足要求的路径，返回true即可，否则遍历完所有路径也没有找到的满足条件的话，返回false；
- 值得注意的是，必须是从父节点到叶子节点，因此，在找到与目标结果相等的结果时，必须判断当前是否为叶子节点；
- 另外，在搜索完一条从父节点到叶子节点的路径，且不满足目标值则须回溯，即减去当前节点值。
代码如下：
public:
bool dfs(TreeNode* root,int& get,int sum){
get+=root->val;//累加路径上的值
if(root->left!=nullptr && dfs(root->left, get,sum)) return true;//左子树上找到
if(root->right!=nullptr && dfs(root->right, get,sum)) return true;//右子树上找到
if(get==sum && root->left==nullptr && root->right==nullptr) return true;
//判断找到与目标值相等情况下，当前节点是否为叶子节点
else get-=root->val;//没找到则回溯
return false;//无满足条件路径返回false
}
bool hasPathSum(TreeNode* root, int sum) {
if(root==nullptr) return false;
int get=0;
return dfs(root, get,sum);
}
};
