Find all k-sum paths in a binary tree

Question

Description:

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

Note: A leaf is a node with no children.

Leetcode

Code:

class Solution {
    private List<List<Integer>> paths = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        traverse(root, sum, new ArrayList<Integer>());
        return paths;
    }

    private void traverse(TreeNode root, int sum, ArrayList<Integer> path) {
        if (root != null) {
            path.add(root.val);

            if (root.left == null && root.right == null && sum == root.val) {
                paths.add((ArrayList) path.clone());
            }

            traverse(root.left,  sum - root.val, path);
            traverse(root.right, sum - root.val, path);

            path.remove(path.size() - 1);
        }
    }
}

Answer 1

It's a fine solution. I have a few minor comments.

• It's easy to overlook that pathSum doesn't clear the content of paths, which will affect the returned value from subsequent calls, which is likely to be unexpected by callers. In this online puzzle it doesn't seem to matter, but I think it's better to avoid any possible confusion.

• The clone with the cast is ugly. The .clone() method except on arrays is a bit controversial, with questionable benefits if any. I suggest to avoid it. You can replace it with a nice clean paths.add(new ArrayList<>(path))

• The signature of traverse would be better to use List instead of ArrayList.

• I would use an early return in traverse, to have less indented code.