Java DFS with int[] array representing tree


  • 0
    J
    public int pathSum(int[] nums) {
        int n = (1 << 4) - 1;
        int[] tree = new int[n];
        Arrays.fill(tree, Integer.MIN_VALUE);
        for (int num : nums) {
            int level = num / 100;
            num = num % 100;
            int index = num / 10;
            int val = num % 10;
            tree[(1 << (level - 1)) + index - 2] = val;
        }
        int[] sum = new int[]{0};
        search(tree, 0, sum);
        return sum[0];
    }
    
    private int search(int[] tree, int index, int[] sum) {
        if (tree[index] == Integer.MIN_VALUE) {
            return 0;
        }
        if (index * 2 + 2 >= tree.length || (tree[index * 2 + 1] == Integer.MIN_VALUE && tree[index * 2 + 2] == Integer.MIN_VALUE)) {
            sum[0] += tree[index];
            return 1;
        }
        int left = search(tree, index * 2 + 1, sum);
        int right = search(tree, index * 2 + 2, sum);
        sum[0] += tree[index] * (left + right);
        return left + right;
    }

Log in to reply
 

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