LeetCode - Path Sum II | Darren's Blog

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        if (root == null)

            return result;

        recursivePathSum(root, sum, new ArrayList<Integer>(), result);

        return result;

    }

 

    /**

     * Recursively find all paths whose sum is given

     * @param root the root of a tree

     * @param sum the given sum

     * @param current values of the nodes in the current path

     * @param result a list that stores all such paths

     */

    private void recursivePathSum(TreeNode root, int sum, ArrayList<Integer> current,

                                  ArrayList<ArrayList<Integer>> result) {

        if (root == null)   // Empty tree

            return;

 

        // It is a leaf and its value is the path sum

        if (root.val == sum && root.left == null && root.right == null) {

            // Add the node into the current path, and store that path before recover the path

            current.add(root.val);

            result.add(new ArrayList<Integer>(current));

            current.remove(current.size()-1);

            return;

        }

 

        // Add the node into the current path, and explore its left subtree and right subtree

        // before recover the path

        current.add(root.val);

        recursivePathSum(root.left, sum-root.val, current, result);

        recursivePathSum(root.right, sum-root.val, current, result);

        current.remove(current.size()-1);

    }

Read full article from LeetCode - Path Sum II | Darren's Blog