112. Path Sum & 113. Path Sum

Published on July 16, 2023

Question

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.

Algorithm

There is an obvious solution using recursion. For each node, you check if it's a leaf node and

You can either use target sum minus each node until it's 0 or not
Or you can have a initial temp value to calculate the sum

And compare the values. Return true if there is a valid node.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) {
            if (root.val == targetSum) {
                return true;
            } else {
                return false;
            }
        } else {
            return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
        } 
    }
}

Question2

This question like a follow up question for the 112. Path Sum. It not only let us to check if it's valid but also requires us to record all the valid path.

Algorithm2

A typical backtracking issue using recursion. With help of helper, we check if the leaf node condition is qualified so we record, Otherwise we go to the left and right node to continue search and accumulate the path node.

Code2

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return res;
        list.add(root.val);
        helper(root, targetSum, list);
        return res;
    }
    
    private void helper(TreeNode root, int targetSum, List<Integer> list) {
        if (root.left == null && root.right == null) {
            if (targetSum == root.val) {
                res.add(new ArrayList<>(list));
                return;
            }
        }
        if (root.left != null) {
            list.add(root.left.val);
            helper(root.left, targetSum - root.val, list);
            list.remove(list.size() - 1);
        }
        if (root.right != null) {
            list.add(root.right.val);
            helper(root.right, targetSum - root.val, list);
            list.remove(list.size() - 1);
        }
    }
}