666.Path Sum IV

Smart

https://leetcode.com/problems/path-sum-iv/discuss/106892/Java-solution-Represent-tree-using-HashMap

class Solution {
    int sum = 0;
    Map<Integer, Integer> map = new HashMap<>();

    public int pathSum(int[] nums) {
        for(int i : nums){
            int key = i / 10;
            int val = i % 10;
            map.put(key, val);
        }
        dfs(nums[0] / 10, 0);
        return sum;
    }
    public void dfs(int root, int curSum){
        int level = root / 10;
        int pos = root % 10;
        int leftChild = (level + 1) * 10 + (2 * pos - 1);
        int rightChild = (level + 1) * 10 + (2 * pos);
        curSum += map.get(root);
        if(!map.containsKey(leftChild) && !map.containsKey(rightChild)){
            sum += curSum;
            return;
        }
        else{
            if(map.containsKey(leftChild))
                dfs(leftChild, curSum);
            if(map.containsKey(rightChild))
                dfs(rightChild, curSum);
        }
    }
}