```
private class Pair {
int sum;
int leafCount;
private Pair(int sum, int leafCount) {
this.sum = sum;
this.leafCount = leafCount;
}
}
public int pathSum(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
return scan(nums, 0).sum;
}
private Pair scan(int[] nums, int i) {
if (i == -1)
return new Pair(0, 0);
int val = nums[i]%10;
int lv = nums[i]/100;
int p = nums[i]/10%10;
Pair lp = scan(nums, findChild(nums, lv+1, 2*p-1, i));
Pair rp = scan(nums, findChild(nums, lv+1, 2*p, i));
int leafCount = Math.max(1, lp.leafCount+rp.leafCount);
return new Pair(lp.sum+rp.sum+val*leafCount, leafCount);
}
private int findChild(int[] nums, int lv, int p, int start) {
for (int i = start; i < nums.length && nums[i]/100 <= lv; i++) {
if (nums[i]/100 == lv && nums[i]/10%10 == p)
return i;
}
return -1;
}
```