[LeetCode] 427. Construct Quad Tree

427. Construct Quad Tree

 

이 문제는 보자마자 전형적인 분할 정복 문제라는 것이 보였고, 4개 분면으로 나눠가며 grid의 특정 범위 내의 모든 수가 같은 케이스에는 isLeaf 값을 참으로 갖는 node를 반환하는 식으로 한다면, size가 1x1인 grid 범위가 될 때 같은 베이스 케이스도 필요 없이 통과할 수 있다 생각해 아래 코드와 같이 작성했습니다.

class Solution {
    public Node construct(int[][] grid) {
        return construct(grid, 0, 0, grid.length, grid[grid.length-1].length);
    }

    public Node construct(int[][] grid, int topLeft_x, int topLeft_y, int bottomRight_x, int bottomRight_y) {

        Node node = new Node(grid[topLeft_x][topLeft_y] == 1, true);

        for (int i = topLeft_x; i < bottomRight_x; i++) {
            for (int j = topLeft_y; j < bottomRight_y; j++) {
                if (grid[topLeft_x][topLeft_y] != grid[i][j]) {
                    node.isLeaf = false;
                }
            }
        }

        if (!node.isLeaf) {
            node.topLeft = construct(grid,
                            topLeft_x,
                            topLeft_y,
                            (topLeft_x + bottomRight_x) / 2,
                            (topLeft_y + bottomRight_y) / 2);
            node.topRight = construct(grid,
                            topLeft_x,
                            (topLeft_y + bottomRight_y) / 2,
                            (topLeft_x + bottomRight_x) / 2,
                            bottomRight_y);
            node.bottomLeft = construct(grid,
                            (topLeft_x + bottomRight_x) / 2,
                            topLeft_y,
                            bottomRight_x,
                            (topLeft_y + bottomRight_y) / 2);
            node.bottomRight = construct(grid,
                            (topLeft_x + bottomRight_x) / 2,
                            (topLeft_y + bottomRight_y) / 2,
                            bottomRight_x,
                            bottomRight_y);
        }

        return node;
    }
}