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


  • 0
    W

    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;
        }
    }
    

Log in to reply
 

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