# [C++] [Java] Clean Code

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

Regardless whether these nodes exist:

the position of left child is always `parent_pos * 2`;
the position of right child is always`parent_pos * 2 + 1`;
the position of parent is always `child_pos / 2`;

Solution C++ Array

``````class Solution {
public:
int pathSum(vector<int>& nums) {
int m[5][8] = {};
for (int n : nums) {
int i = n / 100; // i is 1 based index;
int j = (n % 100) / 10 - 1; // j used 0 based index;
int v = n % 10;
m[i][j] = m[i - 1][j / 2] + v;
}

int sum = 0;
for (int i = 1; i < 5; i++) {
for (int j = 0; j < 8; j++) {
if (i == 4 || m[i][j] && !m[i + 1][j * 2] && !m[i + 1][j * 2 + 1]){
sum += m[i][j];
}
}
}
return sum;
}
};
``````

Solution C++ map
If we use map, we don't need to do the boundary check at little extra cost of memory.

``````class Solution {
public:
int pathSum(vector<int>& nums) {
map<int, map<int, int>> m;
for (int n : nums) {
int i = n / 100 - 1; // i is 0 based index;
int j = (n % 100) / 10 - 1; // j used 0 based index;
int v = n % 10;
m[i][j] = m[i - 1][j / 2] + v;
}

int sum = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 8; j++) {
sum += m[i][j] && !m[i + 1][j * 2] && !m[i + 1][j * 2 + 1] ? m[i][j] : 0;
}
}
return sum;
}
};
``````

Solution C++ - queue

``````class Solution {
public:
int pathSum(vector<int>& nums) {
if (nums.empty()) return 0;
int sum = 0;
queue<info> q;
info dummy(0);
info* p = &dummy; // parent start with dummy info, root have no real parent;
for (int n : nums) {
info c(n); // child;
while (!p->isparent(c) && !q.empty()) {
sum += p->leaf ? p->v : 0;
p = &q.front();
q.pop();
}
p->leaf = false;
c.v += p->v;
q.push(c);
}
while (!q.empty()) {
sum += q.front().v;
q.pop();
}
return sum;
}
private:
struct info {
int i, j, v;
bool leaf;
info(int n) : i(n / 100 - 1), j((n % 100) / 10 - 1), v(n % 10), leaf(true) {};
bool isparent(info other) { return i == other.i - 1 && j == other.j / 2;};
};
};
``````

Solution Java

``````class Solution {
public int pathSum(int[] nums) {
int[][] m = new int[5][8];
for (int n : nums) {
int i = n / 100; // i is 1 based index;
int j = (n % 100) / 10 - 1; // j used 0 based index;
int v = n % 10;
m[i][j] = m[i - 1][j / 2] + v;
}

int sum = 0;
for (int i = 1; i < 5; i++) {
for (int j = 0; j < 8; j++) {
if (i == 4 || m[i][j] != 0 && m[i + 1][j * 2] == 0 && m[i + 1][j * 2 + 1] == 0){
sum += m[i][j];
}
}
}
return sum;
}
}
``````

• The implementation of using an array is very impressive!

• awesome solution :)

• C++ different approach !

``````class Solution {
public:
int pathSum(vector<int>& nums) {
int n = nums.size();
vector<int> temp(16, -1); //As the max depth of tree is 5 the total nodes will be 2^(depth)-1;

for (int i=0;i<n;i++){
string arr = to_string(nums[i]);
int depth = arr[0]-'0';
int level = arr[1]-'0';
int value = arr[2]-'0';
int idx = (1<<(depth-1)) + level - 1; //calculate the index of the node in temp array
temp[idx] = value;
}

int res=0;
for (int i=temp.size()-1;i>0;i--){
//If the node is a leaf i.e. (i>7 || temp[2*i]==-1 && temp[2*i+1]==-1) then sum the path from leaf till the root
if (temp[i] != -1 && (i>7 || (temp[2*i]==-1 && temp[2*i+1]==-1))){
int j=i;
while (j>0){
res += temp[j];
j = j/2;
}
}
}
return res;
}
};
``````

• Nice solution. I tried to do it using BFS at first but ended up resorting to DFS.

• Smart !!!!!!!!

• similar idea.

``````class Solution {
public int pathSum(int[] nums) {
int[] vals=new int[16];
Arrays.fill(vals, -1);

for (int num:nums){
int[] arr=new int[] {num/100, (num%100)/10, num%10};
int index=(int)Math.pow(2, arr[0]-1)-1+arr[1];
vals[index]=arr[2];
}

int sum=0;
for (int i=1;i<=15;i++){
if (vals[i]>=0){
if (vals[i/2]>=0)
vals[i] += vals[i/2];
if (i>=8 || (vals[i*2]==-1 && vals[i*2+1]==-1))
sum += vals[i];
}
}
return sum;
}
}

``````

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