# C++, easy to understand, O(n) 3ms

• We can easily build the tree using a vector<vector<int>>:

``````tree[dep][pos] = val;
``````

If pos of the parent node = k,
left child = 2k
right child = 2k+1

``````       0
0       1
0   1   2   3
0 1 2 3 4 5 6 7
``````

Then iterate through the tree level by level, update path sum from root to each node, and add all leaves to the sum.

``````class Solution {
public:
int pathSum(vector<int>& nums) {
if (nums.empty()) return 0;
vector<int> tree(8, 0);
int dep = nums.back()/100, n = nums.size(), ans = 0;
for (int i = 1, j = 0; i <= dep; i++) {
vector<int> tmp(8, 0);
// fill path sum in nodes of each level
while (j < n && nums[j]/100 == i) {
int pos = nums[j]%100/10-1;
tmp[pos] = nums[j++]%10 + tree[pos/2];
}
// if both children are null, add the parent leaf node
// also work for node value of 0, such as 210
for (int k = 0; k < 4; k++) {
if (tmp[k*2] == 0 && tmp[k*2+1] == 0)
ans += tree[k];
}
swap(tree, tmp);
}
return accumulate(tree.begin(), tree.end(), ans);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.