# LeetCode: 427. 建立四叉树¶

## 1、题目描述¶

• N 将小于 1000 且确保是 2 的整次幂。
• 如果你想了解更多关于四叉树的知识，你可以参考这个 wiki 页面。

## 2、解题思路¶

"""
# Definition for a QuadTree node.
class Node:
def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
"""
class Solution:
def construct(self, grid: [[int]]) -> 'Node':
return self.dfs(grid, 0, len(grid), 0, len(grid))

def dfs(self, grid, x1, x2, y1, y2):
temp = self.judge_leaf(grid, x1, x2, y1, y2)
if temp == 0:
return Node(False, True, None, None, None, None)
elif temp == 1:
return Node(True, True, None, None, None, None)
else:
current_node = Node(True, False, None, None, None, None)
current_node.topLeft = self.dfs(grid, x1, x1 + (x2 - x1) // 2, y1, y1 + (y2 - y1) // 2)
current_node.topRight = self.dfs(grid, x1, x1 + (x2 - x1) // 2, y1 + (y2 - y1) // 2, y2)
current_node.bottomLeft = self.dfs(grid, x1 + (x2 - x1) // 2, x2, y1, y1 + (y2 - y1) // 2)
current_node.bottomRight = self.dfs(grid, x1 + (x2 - x1) // 2, x2, y1 + (y2 - y1) // 2, y2)
return current_node

def judge_leaf(self, grid, x1, x2, y1, y2):
"""

:return: 0: all zero
1: all 1
2: zero and one
"""
temp = sum([grid[x][y] for x in range(x1, x2) for y in range(y1, y2)])
if temp == 0:
return 0
elif temp == (x2 - x1) * (y2 - y1):
return 1
return 2