Algorithm to print the total sum of all the path

Question

Giving you a binary tree which defined as follows:

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

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

print the total sum of all the path, a path is defined as the line from the root node to any leaf node

For example:

4 5 6 7 8 10 # # # # 9

should return:

path1: 4 + 5 + 7

path2: 4 + 5 + 8 + 9

path3: 4 + 6 + 10

so the total path sum should be: path1 + path2 + path3

how can we solve the problem by using

• recursive
• non-recursive

I have find a solution by using non-recursive, but have some little problem about recursive method

Non-Recursive Method:

/**
 * non-recursive
 */
public static int pathSum2(TreeNode root) {
    int sum = 0;
    if (root == null) {
        return sum;
    }
    Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
    Queue<Integer> queueSum = new LinkedList<Integer>();

    queueNode.add(root);
    queueSum.add(root.val);
    while (!queueNode.isEmpty()) {
        TreeNode node = queueNode.poll();
        int temp = queueSum.poll();
        if (node.left == null && node.right == null) {
            sum += temp;
        }
        if (node.left != null) {
            queueNode.add(node.left);
            queueSum.add(node.left.val + temp);
        }
        if (node.right != null) {
            queueNode.add(node.right);
            queueSum.add(node.right.val + temp);
        }
    }
    return sum;
}

Recursive Method:

/**
 * recursive
 */
public List<List<Integer>> pathSum(TreeNode root) {
    List<List<Integer>> rst = new ArrayList<List<Integer>>();

    helper(rst, new ArrayList<Integer>(), root);
    return rst;
}

public void helper(List<List<Integer>> rst, ArrayList<Integer> list,
                   TreeNode root) {
    if (root == null) {
        return;
    }
    list.add(root.val);
    if (root.left == null && root.right == null) {
        rst.add(new ArrayList<Integer>(list));
    }
    helper(rst, list, root.left);
    helper(rst, list, root.right);
    list.remove(list.size() - 1);
}

but in this way, what I have output is all the path, what if I want to get the total sum of those path?

One way to get the answer is iterator the List> and get the answer but I think it's inefficient. How can we deal with this just in the helper() method because for the sum, java is just pass-by-value

Answer 1

I have find a solution by using recursive

/**
 * recursive
 */
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> rst = new ArrayList<List<Integer>>();

    helper(rst, new ArrayList<Integer>(), root, sum);
    return rst;
}

public void helper(List<List<Integer>> rst, ArrayList<Integer> list,
                   TreeNode root, int sum) {
    if (root == null) {
        return;
    }
    list.add(root.val);
    if (root.left == null && root.right == null) {
        rst.add(new ArrayList<Integer>(list));
    }
    helper(rst, list, root.left, sum - root.val);
    helper(rst, list, root.right, sum - root.val);
    list.remove(list.size() - 1);
}