666. Path Sum IV

二刷 06/2022

Version #1 DFS

Time O(N)

Space O(N)

Runtime: 1 ms, faster than 96.05% of Java online submissions for Path Sum IV.

Memory Usage: 39.7 MB, less than 95.39% of Java online submissions for Path Sum IV.

class Solution {

    public int pathSum(int[] nums) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        // Split the numbers into index, value pairs

        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {

            map.put(num / 10, num % 10);

        }

        // Given a node with index x

        // its left child index is:

        // ((x / 10) + 1) * 10 + (x % 10 - 1) * 2 + 1

        // its right child index is:

        // ((x / 10) + 1) * 10 + (x % 10 - 1) * 2 + 2

        // e.g. 11

        //      / \

        //     21 22

        int[] sum = new int[1];

        dfs(map, sum, nums[0] / 10, 0);

        return sum[0];

    }

    

    private void dfs(Map<Integer, Integer> map, int[] sum, int index, int pathSum) {

        int val = map.get(index);

        pathSum += val;

        int leftIndex = (index / 10 + 1) * 10  + (index % 10 - 1) * 2 + 1;

        int rightIndex = leftIndex + 1;

        if (!map.containsKey(leftIndex) && !map.containsKey(rightIndex)) {

            sum[0] += pathSum;

            return;

        }

        if (map.containsKey(leftIndex)) {

            dfs(map, sum, leftIndex, pathSum);

        }

        if (map.containsKey(rightIndex)) {

            dfs(map, sum, rightIndex, pathSum);

        }

    }

}

一刷
Path Sum的精髓是dfs到leaf然后维护一个path sum
在leaf处把这个path sum加到result里面

97.99 %
class Solution {
    public int pathSum(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        // traverse the tree, add path sum at leaf
        int[] result = new int[1];
        // key-id, value-value
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num / 10, num % 10);
        }
        dfs(nums[0] / 10, map, 0, result);
        return result[0];
    }
    private void dfs(int id, Map<Integer, Integer> map, int path, int[] result) {
        int val = map.get(id);
        path += val;
        //[113, 215, 221]
        int left = id + 10 + id % 10 - 1;
        int right = id + 10 + id % 10;
        if (!map.containsKey(left) && !map.containsKey(right)) {
            result[0] += path;
            return;
        }
        if (map.containsKey(left)) {
            dfs(left, map, path, result);
        }
        if (map.containsKey(right)) {
            dfs(right, map, path, result);
        }
    }
}