二叉树之路径总和

路径总和

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

示例 1：
注图片转载自leetcode官网
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

class Solution {
    int sum = 0;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        sum += root.val;
        if(sum == targetSum && root.left == null && root.right == null) return true;
        boolean leftVal = hasPathSum(root.left, targetSum);
        boolean rightVal = hasPathSum(root.right, targetSum);
        sum -= root.val;
        return leftVal || rightVal;
    }
}

路径总和II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。叶子节点是指没有子节点的节点。

示例 1：

注图片转载自leetcode官网
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

class Solution {
    List<List<Integer>> ans;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        int sum = 0;
        tarversal(root, targetSum, list, sum);
        return ans;
    }
    private void tarversal(TreeNode root, int targetSum, List<Integer> list, int sum){
        if(root == null) return;
        sum += root.val;
        list.add(root.val);
        if(root.left == null && root.right == null){
            if(sum == targetSum){
                ans.add(new ArrayList<>(list));
            }
        }
        tarversal(root.left, targetSum, list, sum);
        tarversal(root.right, targetSum, list, sum);
        sum -= root.val;
        list.remove(list.size() - 1);
    }
}

        与上一题相比，这题要求找到所有从根结点到叶子结点路径总和等于targetSum的路径，而上一题仅找出一条即可。这里详细说明上述代码的执行流程。首先定义一个list集合用于收集某条路径上的结点，sum用于记录对应路径的和。对应的结点的左右子树遍历完成后，将对应结点从list集合移除，sum减去对应结点的值，即为回溯的过程。
        接着进入tarversal方法。首先遍历根结点5，之后sum += 5，sum等于5，将根结点5的值放入list集合中，list为[5]。接着if判断根结点是否为叶子结点，显然不为叶子结点，递归进入根结点的left，sum += 4，sum等于9，将结点4加入list集合中，list为[5, 4]。接着if判断结点4是否为叶子结点，显然不为叶子结点，递归进入结点4的left，sum += 11，sum等于20，将结点11加入list集合中，list为[5, 4, 11]。接着if判断结点11是否为叶子结点，显然不为叶子结点，递归进入结点11的left，sum += 7，sum为27，将7加入list集合中，list为[5, 4, 11, 7]，之后if判断结点7是否为叶子结点，显然结点7为叶子结点，但是sum不等于targetSum(22)，继续递归进入结点7的left，因为结点7的left为空，递归返回，递归进入结点7的right，right为空，递归返回，结点7左右子树遍历完成，sum -= 7，sum为20，将结点7从list集合中移除，list为[5, 4, 11]。递归返回，并进入结点11的right，将sum += 2，sum为22，将结点2加入list集合，list集合为[5, 4, 11, 2]，接着if判断结点2是否为叶子结点，显然结点2为叶子结点，并且此时sum等于targetSum，重新创建一个集合将list中的所有值传入该集合，并放入ans中。递归进入结点2的left，为空，返回，递归进入结点2的right，为空，返回，结点2的左右子树遍历完成，sum -= 2，sum为20，将结点2从list中移除，list为[5, 4, 11]。递归返回结点11，结点11的左右子树遍历完成，将sum -= 11，sum为9，将结点11从list集合中移除，list为[5, 4]。递归返回结点4，进入结点4的right，为空，返回。结点4的左右子树遍历完成，sum -= 4，sum等于5，将结点4从list集合中移除，list为[5]。递归返回根结点5，此时根结点5的左子树遍历完成，按上述过程继续递归根结点的右子树，就可以得到路径和等于targetSum的所有路径。

路径总和III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

注图片转载自leetcode官网
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

class Solution {
    int ans = 0;
    public int pathSum(TreeNode root, int targetSum) {
        tarversal(root, targetSum);
        return ans;
    }
    private void tarversal(TreeNode root, long targetSum){
        if(root == null) return;
        tarverSum(root, targetSum);
        tarversal(root.left, targetSum);
        tarversal(root.right, targetSum);
    }
    private void tarverSum(TreeNode root, long targetSum){
        if(root == null) return;
        targetSum -= root.val;
        if(targetSum == 0){
            ans++;
        }
        tarverSum(root.left, targetSum);
        tarverSum(root.right, targetSum);
    }
}

        之前的两道题要求路径必须从根结点出发，到叶子结点，而这道题，可以是根结点到叶子结点的其中一段路径，不一定要从根结点出发，不一定以叶子结点作为尾结点。这题的解题思路就是遍历所有结点，将每个结点都作为根结点，在tarversal方法中，采用前序遍历的方式遍历所有结点，每次将每个结点作为根结点，调用tarverSum方法，将当前结点和targetSum传入tarverSum方法中。在tarverSum方法中，以当前传入结点作为起始结点，采用前序遍历的方式，每次targetSum减去遍历到的结点值，如果targetSum的值为0时，表示存在一条路径。
        下面详细描述上述代码的执行过程。首先tarversal方法中遍历根结点，将根结点10以及targetSum(8)传入tarverSum方法中。在tarverSum中，tarverSum -= 10，tarverSum等于-2，不为0，接着遍历结点10的left，将-2传入tarverSum中，tarverSum -=5，tarverSum = -7，不为0，接着遍历结点5的left，将-7传入tarverSum中，tarverSum -= 3，tarverSum = -10，不为0，接着遍历结点3的left，将-10传入tarverSum中，tarverSum -= 3，tarverSum = -13，不为0，接着遍历结点3的left，为空返回，接着遍历结点3的right，为空返回。结点3的左右子树遍历完成，递归返回上一个结点3，继续上一个结点3的right，将-10传入tarverSum中，tarverSum -= -2，tarverSum等于-12，不为0，接着递归结点-2的left，为空返回，接着遍历结点-2的right，为空返回。结点-2的左右子树遍历完成，递归返回结点-3。-3的左右子树遍历完成，递归返回结点5。递归进入结点5的right，将-7传入tarverSum中，如此重复上述过程，即可完成以结点10为根结点的所有路径的遍历。
        之后以5, 3, 3, -2…为分别为根结点重复上述过程，即可找到所有路径和为targetSum的路径数。