# Python 1D Array Solution, 55 ms

• This solution uses a 1 dimensional array to represent the binary tree and index arithmetic to traverse it. From any node at index location i, the left node is at i+i+1 and right node is at i+i+2.

def pathSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a = [None for i in xrange(32)]
for n in nums:
t = n % 100
v = n % 10
p = (t - v) / 10
d = (n - t) / 100
a[2**(d-1)-1 + (p-1)] = v
def dfs(i, s):
if a[i] == None:
return 0
s += a[i]
l = dfs(2*i + 1, s)
r = dfs(2*i + 2, s)
if l == 0 and r == 0:
return s
return l + r
s = dfs(0, 0)
return s

• C++ version completes in 6 ms. I used a hash instead of array, same time complexity.

class Solution {
public:
unordered_map<int, int> a;
int dfs(int i, int s) {
if (a.find(i) == a.end()) {
return 0;
}
s += a[i];
int l = dfs(i+i+1, s);
int r = dfs(i+i+2, s);
if (!l && !r) {
return s;
}
return l + r;
}

int pathSum(vector<int>& nums) {
for (auto n: nums) {
int t = n % 100;
int v = n % 10;
int p = (t - v) / 10;
int d = (n - t) / 100;
a[int(pow(2, (d-1)))-1 + (p-1)] = v;
}
return dfs(0, 0);
}
};

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