112. 路径总和(较难)

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false

示例 3：

输入：root = [1,2], targetSum = 0
输出：false

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

回溯

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }
        //这个参数没理解
        return backtrack(root,targetSum-root.val);
    }
    public boolean backtrack(TreeNode root,int sum){
        if(root.left==null && root.right==null&&sum==0){
            return true;
        }
        if(root.left!=null){
            sum -= root.left.val;
            if(backtrack(root.left,sum)){
                return true;
            }
            sum += root.left.val;
        }
        if(root.right!=null){
            sum-=root.right.val;
            if(backtrack(root.right,sum)){
                return true;
            }
            sum+=root.right.val;
        }
        return false;
    }
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        //卧槽，还有一个限制条件
        if(root==null){
            return false;
        }
        //深搜递归
        if(root.left==null && root.right==null){
            return root.val==targetSum;
        }
        return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
    }
}

代码3：自己写的回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }
        return backtrack(root,targetSum);
    }
    public boolean backtrack(TreeNode root,int targetSum){
        //终止条件
        if(root.left==null && root.right==null ){
            return root.val==targetSum;
        }
        //子集树回溯
        if(root.left!=null){
            targetSum -=root.val;
            if(backtrack(root.left,targetSum)){
                return true;
            }
            targetSum += root.val;
        }
        if(root.right!=null){
            targetSum -=root.val;
            if(backtrack(root.right,targetSum)){
                return true;
            }
            targetSum +=root.val;
        }
        return false;
    }
}