666. Path Sum IV

If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.
For each integer in this list:
The hundreds digit represents the depth D of this node, 1 <= D <= 4.
The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
The units digit represents the value V of this node, 0 <= V <= 9.
Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.
Example 1:
Input: [113, 215, 221]
Output: 12
Explanation:
The tree that the list represents is:
3
/ \
5 1
The path sum is (3 + 5) + (3 + 1) = 12.

昨天没写出来（看了别人的思路，但是dfs写不过去，backtracking遇到了问题），带着疑问睡觉，夜里一直在半梦半醒地想着这题的代码，烦。我一开始想的是完全按照树的那惯用写法，让dfs的下一层处理node为空的情况，所以我判断了一下如果map里没有leftKey或者rightKey就将它置为-1，以标识node为空，但这样backtrackiing遇到了麻烦，我发现leftKey和rightKey没有恢复回去。事实上上面的想法本身就是错的，因为只有左右子树都为空的时候，才能说走到了一个path的结束。

早上梳理了一遍，dfs可以用这样的思路写：

1. 如果当前节点是null，返回；
2. 否则，如果左右节点都是null，加入当前节点的值到single、sum里，返回；
3. 递归执行左右子树，第三个参数带上当前路径的和

int sum = 0;

    public int pathSum(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i] / 10, nums[i] % 10);
        }
        dfs(map, nums[0] / 10, 0);
        return sum;
    }

    //  Input: [113, 215, 221]
    private void dfs(Map<Integer, Integer> map, int key, int singlePathSum) {
        if (!map.containsKey(key)) {
            return;
        }
        int leftKey = (key / 10 + 1) * 10 + (key % 10) * 2 - 1;
        int rightKey = leftKey + 1;
        if (!map.containsKey(leftKey) && !map.containsKey(rightKey)) {
            singlePathSum += map.get(key);
            sum += singlePathSum;
            return;
        }
        dfs(map, leftKey, singlePathSum + map.get(key));
        dfs(map, rightKey, singlePathSum + map.get(key));
    }

solutions里的写法，可以看出基本数据类型的dfs即便不放到dfs的参数里，也不需要恢复现场：

class Solution {
    int sum = 0;
    Map<Integer, Integer> tree = new HashMap<>();
    
    public int pathSum(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        for (int num : nums) {
            int key = num / 10;
            int value = num % 10;
            tree.put(key, value);
        }
        
        traverse(nums[0] / 10, 0);
        
        return sum;
    }
    
    private void traverse(int root, int preSum) {
        int level = root / 10;
        int pos = root % 10;
        int left = (level + 1) * 10 + pos * 2 - 1;
        int right = (level + 1) * 10 + pos * 2;
        
        int curSum = preSum + tree.get(root);
        
        if (!tree.containsKey(left) && !tree.containsKey(right)) {
            sum += curSum;
            return;
        }
        //traverse之前判断了是否有左右孩子，避免下一层判断
        if (tree.containsKey(left)) 
              traverse(left, curSum);
        if (tree.containsKey(right)) 
              traverse(right, curSum);
    }
}