题解 | #二叉树中和为某一值的路径(一)#

递归+回溯

思路： 与大部分解法一样，考虑用前序遍历，遍历任意一条路径到叶子节点并记录路径上的和，如果此时和与目标结果相等则找到满足要求的路径，返回true即可，否则遍历完所有路径也没有找到的满足条件的话，返回false；

1. 值得注意的是，必须是从父节点到叶子节点，因此，在找到与目标结果相等的结果时，必须判断当前是否为叶子节点；
2. 另外，在搜索完一条从父节点到叶子节点的路径，且不满足目标值则须回溯，即减去当前节点值。

代码如下：

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);
    }
};