427. Construct Quad Tree - Medium

前往題目

想法

• 讀不懂題目:D

思路

第一次看到這種題，其實目的就只是分成一堆正方形，每個正方形裡面數值都一樣，並建立樹

1. DFS，每次都先檢查當前正方形裡是否數值完全相同(一開始是整個大正方形)
2. 是的話直接回傳node，不是的話切割當前正方形為四象限每個象限再各自檢查是否數值相同
3. 最後形成node，並加入子節點們，形成樹

Code

class Solution {

    public Node construct(int[][] grid) {
        return dfs(grid, grid.length, 0, 0);
    }

    private Node dfs(int[][] grid, int n, int r, int c) {
        boolean allSame = true;

        // Check if all the values in the current area are the same
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                // Not the same, comparing to the original cell
                if (grid[r][c] != grid[r + i][c + j]) {
                    allSame = false;
                    break;
                }
            }
        }

        // All the same! This could be a node
        if (allSame) return new Node(grid[r][c] != 0, true);

        // Not the same, so split the square into squares
        n = n / 2;

        // Obtain each quadrant
        Node topLeft = dfs(grid, n, r, c);
        Node topRight = dfs(grid, n, r, c + n);
        Node bottomLeft = dfs(grid, n, r + n, c);
        Node bottomRight = dfs(grid, n, r + n, c + n);
        // Build the tree
        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }
}