666. Path Sum IV

If the depth of a tree is smaller than 5, then this tree can be represented by an array of three-digit integers. For each integer in this array:

• The hundreds digit represents the depth d of this node where 1 <= d <= 4.
• The tens digit represents the position p of this node in the level it belongs to where 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 where 0 <= v <= 9.

Given an array of ascending three-digit integers nums representing a binary tree with a depth smaller than 5, return the sum of all paths from the root towards the leaves.

It is guaranteed that the given array represents a valid connected binary tree.

class Solution {
    int tree[6][33];
    int res = 0;
    void dfs(int d, int l, int sum) {
        int nd = d + 1, lc = l * 2 - 1, rc = l * 2;
        sum += tree[d][l];
        if(nd == 6 or (tree[nd][lc] == -1 and tree[nd][rc] == -1)) {
            res += sum;
        } else {
            if(tree[nd][lc] != -1) dfs(nd,lc,sum);
            if(tree[nd][rc] != -1) dfs(nd,rc,sum);
        }
    }
public:
    int pathSum(vector<int>& nums) {
        memset(tree, -1, sizeof tree);
        for(auto& n : nums) {
            int d = n / 100, l = (n / 10) % 10, v = n % 10;
            tree[d][l] = v;
        }
        dfs(1,1,0);
        return res;
    }
};