leetcode-javascript/solutions/0427-construct-quad-tree.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Construct Quad Tree
 * Time Complexity: O(N^2)
 * Space Complexity: O(N^2)
 */
var construct = function (gridMatrix) {
    function processSubgrid(rowStart, colStart, currentSize) {
        const initialQuadrantValue = gridMatrix[rowStart][colStart];
        let isUniform = true;

        outerLoop:
        for (let rowIterator = rowStart; rowIterator < rowStart + currentSize; rowIterator++) {
            for (let colIterator = colStart; colIterator < colStart + currentSize; colIterator++) {
                if (gridMatrix[rowIterator][colIterator] !== initialQuadrantValue) {
                    isUniform = false;
                    break outerLoop;
                }
            }
        }

        if (isUniform) {
            return new _Node(initialQuadrantValue === 1, true, null, null, null, null);
        } else {
            const halfSize = currentSize / 2;
            const topLeftNode = processSubgrid(rowStart, colStart, halfSize);
            const topRightNode = processSubgrid(rowStart, colStart + halfSize, halfSize);
            const bottomLeftNode = processSubgrid(rowStart + halfSize, colStart, halfSize);
            const bottomRightNode = processSubgrid(rowStart + halfSize, colStart + halfSize, halfSize);

            return new _Node(true, false, topLeftNode, topRightNode, bottomLeftNode, bottomRightNode);
        }
    }

    return processSubgrid(0, 0, gridMatrix.length);
};