# Using one-dimension array to store the entire tree, beats 97%.

• Key idea is: given a num, sperate its level, position and value, then calculate its correspond pos in 1 dimension array and fill the value.
Traverse the tree array from right to left, use a boolean array to trace the leaf nodes visited. By using the formular: root_pos = leaf_pos / 2. You can recursively traverse the tree from left to root.

``````class Solution {
public int pathSum(int[] nums) {
int[] tree = new int[64+1];
boolean[] visited = new boolean[64+1];
Arrays.fill(visited, true);
for(int num: nums) {
int lev = num / 100 - 1;
int pos = num / 10 % 10 - 1;
int v = num % 10;
tree[(int)Math.pow(2, lev) + pos] = v;
visited[(int)Math.pow(2, lev) + pos] = false;
}
int sum = 0;
for(int i = tree.length - 1; i >= 0; i--) {
if(!visited[i]) {
visited[i] = true;
int cur = i;
while(cur != 0) {
sum += tree[cur];
visited[cur] = true;
cur /= 2;
}
}
}
return sum;
}
}
``````

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