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

深度优先搜索+剪枝

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool dfs(TreeNode* root,int target){
        if(!root || target == 0)  return false;//走到头了或者已经满足了和依然没有满足要求说明这条路径查找失败
        target -= root->val;//目标值减去已经走过的
        if(target == 0 && !root->left&& !root->right) return true;//满足和并且该节点是叶子节点
        return dfs(root->left,target) || dfs(root->right,target);
    }//只要左右两种选择有一个符合条件就可以，所以是或
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        return dfs(root,sum);
    }
};