Problem #427: Construct Quad Tree

Intuition & Strategy Breakdown

Recursively construct QuadTree: if grid region has uniform values create leaf node, else construct 4 sub-quadrants.

Python Solution

class Solution:
    def construct(self, grid: List[List[int]]) -> "Node":
        def build(x, y, L):
            if L == 1:
                return Node(grid[x][y] == 1, True, None, None, None, None)
            half = L // 2
            tl = build(x, y, half)
            tr = build(x, y + half, half)
            bl = build(x + half, y, half)
            br = build(x + half, y + half, half)
            if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf:
                if tl.val == tr.val == bl.val == br.val:
                    return Node(tl.val, True, None, None, None, None)
            return Node(True, False, tl, tr, bl, br)
        return build(0, 0, len(grid))

Java Solution

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

    private Node build(int x, int y, int L, int[][] grid) {
        if (L == 1) {
            return new Node(grid[x][y] == 1, true, null, null, null, null);
        }
        int half = L / 2;
        Node tl = build(x, y, half, grid);
        Node tr = build(x, y + half, half, grid);
        Node bl = build(x + half, y, half, grid);
        Node br = build(x + half, y + half, half, grid);
        if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf
                && tl.val == tr.val && tr.val == bl.val && bl.val == br.val) {
            return new Node(tl.val, true, null, null, null, null);
        }
        return new Node(true, false, tl, tr, bl, br);
    }
}