package q427

type Node struct {
	Val         bool
	IsLeaf      bool
	TopLeft     *Node
	TopRight    *Node
	BottomLeft  *Node
	BottomRight *Node
}

func mkTree(grid [][]int, x, y, w int) *Node {
	if w == 1 {
		return &Node{
			Val:    grid[y][x] == 1,
			IsLeaf: true,
		}
	}

	subtreeW := w / 2
	node := &Node{
		TopLeft:     mkTree(grid, x, y, subtreeW),
		TopRight:    mkTree(grid, x+subtreeW, y, subtreeW),
		BottomLeft:  mkTree(grid, x, y+subtreeW, subtreeW),
		BottomRight: mkTree(grid, x+subtreeW, y+subtreeW, subtreeW),
	}
	if !node.TopLeft.IsLeaf || !node.TopRight.IsLeaf || !node.BottomLeft.IsLeaf || !node.BottomRight.IsLeaf {
		return node
	}
	if node.TopLeft.Val && node.TopRight.Val && node.BottomLeft.Val && node.BottomRight.Val ||
		!node.TopLeft.Val && !node.TopRight.Val && !node.BottomLeft.Val && !node.BottomRight.Val {
		return &Node{
			Val:    node.TopLeft.Val,
			IsLeaf: true,
		}
	}
	return node
}

func construct(grid [][]int) *Node {
	return mkTree(grid, 0, 0, len(grid))
}

var _ = construct