Java Solution, using array to rebuild the tree


  • 0
    int sum;
    public int pathSum(int[] nums) {
        sum = 0;
        if (nums == null || nums.length == 0) return 0;
        int[][] levels = new int[4][];
        for (int i = 0; i < 4; i++) {
            levels[i] = new int[(int)Math.pow(2,i)];
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < levels[i].length; j++) {
                levels[i][j] = -1; // initialize the tree, use -1 to mark null
            }
        }
        // Insert nodes to the tree
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i] % 10;
            nums[i] /= 10;
            int pos = nums[i] % 10;
            nums[i] /= 10;
            int row = nums[i] % 10;
            levels[row - 1][pos - 1] = val;
        }
        getSum(levels, 0, 0, 0);
        return sum;
        
    }
    private void getSum(int[][] levels, int i, int j, int pathSum) {
        pathSum += levels[i][j];
        if (i == 3 || levels[i+1][j*2] == -1 && levels[i+1][j*2 + 1] == -1) { // at the last level, or left and right children are null
            sum += pathSum;
        }
        else {
            if (levels[i+1][j*2] != -1) {
                getSum(levels, i + 1,  j * 2 ,  pathSum);
            }
            if (levels[i+1][j*2 + 1] != -1) {
                getSum(levels, i + 1,  j * 2 + 1,  pathSum);
            }
        }
    }

Log in to reply
 

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