UserJS UserJS - 5 months ago 31
Java Question

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

Why is "path.remove(path.size()-1)" used in the end?

This code is for finding all root to leaf paths whose sum is equal to given sum.

public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
ArrayList<Integer> path = new ArrayList<Integer>();
pathSumRe(root, sum, res, path);
return res;
}
public void pathSumRe(TreeNode root, int sum, List<List<Integer>> res,
ArrayList<Integer> path) {

if (root == null)
return;

path.add(root.val);

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

ArrayList<Integer> tmp = new ArrayList<Integer>(path);
res.add(tmp);
}

pathSumRe(root.left, sum - root.val, res, path);
pathSumRe(root.right, sum - root.val, res, path);
path.remove(path.size() - 1);
}


Removing "path.remove(path.size() - 1);" from the code will give the following output.

Input: [0,1,1], 1

Output: [[0,1],[0,1,1]] ==> This is the wrong output

Expected Output: [[0,1],[0,1]]

Answer

The path.remove(path.size() - 1) is removing the last added node from the path list, as you are reusing the same list for all recursive iterations and are adding the current node with path.add(root.val); in each method execution.


The following would be equivalent without reusing the same list (and creating a new one for each execution):

public void pathSumRe(TreeNode root, int sum, List<List<Integer>> res,
        ArrayList<Integer> path) {
    if (root == null) {
        return;
    }
    path.add(root.val);
    if (root.left == null && root.right == null && root.val == sum) {
        res.add(new ArrayList<Integer>(path));
    }
    pathSumRe(root.left, sum - root.val, res, new ArrayList<Integer>(path));
    pathSumRe(root.right, sum - root.val, res, new ArrayList<Integer>(path));
}

This is easier to understand, but creates way more new ArrayLists (depending on the tree structure). Regardless of your edit, both versions are working correctly for a TreeNode like this:

class TreeNode {
    public final int val;
    public final TreeNode left;
    public final TreeNode right;

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}