Java DFS Solution, List instead of Map


  • 0
    A
        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) {
                    count++;
                }
                acc.set(i, acc.get(i) - root.val);
            }
            if (sum - root.val == 0) {
                count++;
            }
            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.