老师，您好，这道题我第一反应的解法

来源：7-6 稍复杂的递归逻辑 Path Sum III

Sky_YiBai

2020-07-06

老师，您好，这道是我第一反应的解法，运行结果不正确，但是我看了您的解法后，还是没明白自己的思路错在哪儿了？

public static int pathSum(TreeNode root, int sum) {
	        if (root == null) {
	        	return 0;
	        }
	        
	        
	        int res = 0;
	        if (root.val == sum) {
	        	res+=1;
	        }
	        
	        res += pathSum(root.left, sum - root.val);
	        res += pathSum(root.left, sum);
	        
	        res += pathSum(root.right, sum - root.val);
	        res += pathSum(root.right, sum);
	        
	        return res;
	    }

写回答

3回答

liuyubobobo

2020-07-07

如果我没有理解错，你的：

res += pathSum(root.left, sum);

res += pathSum(root.right, sum);

两句话是想求从 root.left 或者 root.right 起始，看是不是能重新得到题目初始要求的那个 sum。但是在递归过程中，这个 sum 在变，这个 sum 可能不是题目初始要求的那个 sum。

继续加油！：）

Potter520

2022-07-25

var pathSum = function (root, sum) {

    let paths = [];
    function dfs(root, sum) {
        if (root == null) {
            return 0;
        }

        let res = 0;
        let path = [];
        if (root.val == sum) {
            res += 1;
            path.push(root.val);
            paths.push(path);
        }

        res += dfs(root.left, sum - root.val);
        res += dfs(root.left, sum);

        res += dfs(root.right, sum - root.val);
        res += dfs(root.right, sum);

        return res;
    }

    let ret = dfs(root, sum);
    console.log(paths);

    return ret;
}