112&113&437. Path Sum I &II&III

112.Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

My Solutions:

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return targetSum == root.val;
    return (hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val));
}

113.Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

My Solutions:

和112类似，但是需要记录path。因此在dfs的时候，需要带上list，存入走过的路径的节点。

• dfs/recursive：注意在dfs一个root的两边之后，需要删除list里最后一个节点。这是因为list里记录了走过的每一个节点，但是如果一个节点并不是最后加到最终结果里面去的路径，需要把沿路的节点删除掉。

public class Solution {
    
    //recursive
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList();
        if (root == null) return res;
        dfs(root, sum, res, new ArrayList<Integer>());
        return res;
    }
    
    private void dfs(TreeNode root, int target, List<List<Integer>> res, List<Integer> list) {
        if (root == null) return;
        list.add(root.val); // 记录路上的节点
        
        // 代表走到了叶子节点，并且路径的值等于目标值
        if (root.left == null && root.right == null && root.val == target) res.add(new ArrayList(list));
        
        dfs(root.left, target - root.val, res, list);
        dfs(root.right, target - root.val, res, list);
        
        list.remove(list.size() - 1); // 注意这里删除了list里最后一个节点
    }
}

也可以用bfs/iteratvie 的方法

//iterative
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    int SUM = 0;
    TreeNode cur = root, pre = null;
    
    while (cur != null || !stack.isEmpty()){
        while(cur != null){
            stack.push(cur);
            path.add(cur.val);
            SUM += cur.val;
            cur = cur.left; // 先往左边走到底
        }
        cur = stack.peek();
        if (cur.right != null && cur.right != pre){ // 往右边走到底
            cur = cur.right;
            continue;
        } 
        // 代表走到了叶子节点，并且路径的值等于目标值
        if (cur.left == null && cur.right == null && SUM == sum) 
            res.add(new ArrayList<Integer>(path));

        pre = cur;
        stack.pop();
        // 这里和recursive的思路一样，因为这个节点不在路径上，需要删掉
        path.remove(path.size() - 1); 
        SUM -= cur.val;
        cur = null;
    }
    return res;

437.Path Sum III

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

My Solutions:

这道题不再需要从root出发，也不用一定要到叶子节点，只要路上有满足要求的路径，就算作满足条件的路径。所以一颗以root为根的树，其路径和等于sum的路径个数可由以下三部分组成：

1.路径以root 开头；2.路径不以root开头

• 2.1左子树中等于sum的路径个数

• 2.2右子树中等于sum的路径个数

方法1：

public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    Map<Long, Integer> map = new HashMap<>();
    // 用map储存 <prefix sum> --> <frequency>
    map.put((long)0, 1);
    return helper(root, (long)0, sum, map);
}
    
private int helper(TreeNode node, long total, int sum, Map<Long, Integer> map) {
    if (node == null) return 0;
    
    // update the prefix sum by adding the current node's value
    total += node.val;
    
    // get the number of valid path, ended by current node
    int pathSumToCurrentNode = map.getOrDefault((long)total - sum, 0);

    // update the map with current total
    map.put((long)total, map.getOrDefault((long)total, 0) + 1);

    int res = pathSumToCurrentNode 
        + helper(node.left, total, sum, map) 
            + helper(node.right, total, sum, map) ;

    // restore the map
    map.put((long)total, map.get(total) - 1);        
    return res;
}

方法2: （2023年无法通过test，因为数字太大）

[1000000000,1000000000,null,294967296,null,1000000000,null,1000000000,null,1000000000]

0

Space: O(n) due to recursion.

Time: O(n^2) in the worst case (no branching); O(nlogn) in the best case (balanced tree).

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