Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path’s sum equals targetSum.

leaf is a node with no children.

Example:

Path Sum – II
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]]
import java.util.ArrayList;
import java.util.List;

/**
 * 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 List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<Integer> current = new ArrayList<>();
        generatePathSum(root, current, result, sum);
        return result;
    }

    private void generatePathSum(TreeNode node, List<Integer> current,
                                 List<List<Integer>> result, int sum) {
        if (node == null) {
            return;
        }
        current.add(node.val);
        sum = sum - node.val;
        if (sum == 0 && node.left == null && node.right == null) {
            result.add(new ArrayList<>(current));
            current.remove(current.size() - 1);
            return;
        }
        generatePathSum(node.left, current, result, sum);
        generatePathSum(node.right, current, result, sum);
        current.remove(current.size() - 1);
    }
}

Categories: Binary Tree

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s