Java DFS Solution, List instead of Map

  • 0
        public int pathSum(TreeNode root, int sum) {
            return pathSum(root, sum, new ArrayList<>());
        private int pathSum(TreeNode root, int sum, List<Integer> acc) {
            if (root == null) {
                return 0;
            int count = 0;
            for (int i = 0; i < acc.size(); i++) {
                if (acc.get(i) - root.val == 0) {
                acc.set(i, acc.get(i) - root.val);
            if (sum - root.val == 0) {
            acc.add(sum - root.val);
            return count + pathSum(root.left, sum, new ArrayList<>(acc))
                                + pathSum(root.right, sum, acc);

    The basic idea is the same as the one with map - we accumulate all possible paths to list and subtract current node value from all of them while moving recursively.
    Obviously, this one is much slower than map one, but I thought it might be interesting as alternative.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.