Java Easy to Understand. Using Array.


  • 0
    6

    We can index tree as the parent node is i and two child nodes are 2i and 2i+1.

           i
    2*i       2*i+1
    

    Since the depth of the tree is less than 5, we can create an array of 32.
    We can assign the value of each node to the corresponding position in the array by doing an easy calculation. Remember that the root node is 1.

    
    for(int n : nums) {
         int i = n % 10;
         int j = n/10 % 10;
         int k = n/100;
         arr[(1 << (k-1)) + (j-1)] = i;
    }
    

    When calculating the path, we can go through the array in reverse order and check whether the node is the leaf node. The code is as below:

        public int pathSum(int[] nums) {
            int[] arr = new int[32];
            Arrays.fill(arr, -1);
            for(int n : nums) {
                int i = n % 10;
                int j = n/10 % 10;
                int k = n/100;
                arr[(1 << (k-1)) + (j-1)] = i;
            }
            
            int sum = 0;
            for(int i = arr.length-1; i >= 0; i--) {
                if(arr[i] != -1 && (i >= arr.length/2 || (i < arr.length/2 && arr[i*2] == -1 && arr[i*2+1] == -1))) {
                    int n = i;
                    while(n > 0) {
                        sum += arr[n];
                        n /= 2;
                    }
                }
            }
            return sum;
        }
    

Log in to reply
 

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