44 lines
1,021 B
Go
44 lines
1,021 B
Go
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
|