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

1.思路：

既然是检查从根到叶子有没有一条等于目标值的路径，那肯定需要从根节点遍历到叶子，我们可以在根节点每次往下一层的时候，将sum减去节点值，最后检查是否完整等于0. 而遍历的方法我们可以选取二叉树常用的递归前序遍历，因为每次进入一个子节点，更新sum值以后，相当于对子树查找有没有等于新目标值的路径，因此这就是子问题，递归的三段式为：

1. 终止条件： 每当遇到节点为空，意味着过了叶子节点，返回。每当检查到某个节点没有子节点，它就是叶子节点，此时sum减去叶子节点值刚好为0，说明找到了路径。
2. 返回值： 将子问题中是否有符合新目标值的路径层层往上返回。
3. 本级任务： 每一级需要检查是否到了叶子节点，如果没有则递归地进入子节点，同时更新sum值减掉本层的节点值。

具体做法：

• step 1：每次检查遍历到的节点是否为空节点，空节点就没有路径。
• step 2：再检查遍历到是否为叶子节点，且当前sum值等于节点值，说明可以刚好找到。
• step 3：检查左右子节点是否可以有完成路径的，如果任意一条路径可以都返回true，因此这里选用两个子节点递归的或。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */

    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        if(!root)
            return false;
        if(!root->right && !root->left && sum-(root->val) == 0)
            return true;
        return hasPathSum(root->left, sum-(root->val)) || hasPathSum(root->right, sum-(root->val));
    }
};