【leetcode】427. Construct Quad Tree

题目如下：

解题思路：递归，不是叶子节点就继续拆分成上下左右四个子节点。

代码如下：

"""
# Definition for a QuadTree node.
class Node(object):
    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(object):
    def construct(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: Node
        """
        def check(tl_x,tl_y,br_x,br_y):
            count = 0
            for i in range(tl_x,br_x):
                for j in range(tl_y,br_y):
                    count += grid[i][j]
            if count == 0:
                return 0
            elif count == (br_x - tl_x) * (br_y - tl_y):
                return 1
            return -1

        def connect(parent,child,direction):
            if direction == 'TL':
                parent.topLeft = child
            if direction == 'TR':
                parent.topRight = child
            if direction == 'BL':
                parent.bottomLeft = child
            if direction == 'BR':
                parent.bottomRight = child

        def recursive(tl_x,tl_y,br_x,br_y,parent,direction):
            if check(tl_x,tl_y,br_x,br_y) == 0:
                node = Node(0,True,None,None,None,None)
                if self.root == None:
                    self.root = node
                else:
                    connect(parent,node,direction)
            elif check(tl_x,tl_y,br_x,br_y) == 1:
                node = Node(1,True,None,None,None,None)
                if self.root == None:
                    self.root = node
                else:
                    connect(parent,node,direction)
            else:
                node = Node('*',False,None,None,None,None)
                mid_x = (br_x + tl_x)/2
                mid_y = (br_y + tl_y)/2
                if self.root == None:
                    self.root = node
                else:
                    connect(parent,node,direction)
                recursive(tl_x,tl_y,mid_x,mid_y,node,'TL')
                recursive(tl_x, mid_y, mid_x, br_y, node, 'TR')
                recursive(mid_x, tl_y, br_x, mid_y , node, 'BL')
                recursive(mid_x, mid_y, br_x, br_y, node, 'BR')

        self.root = None
        recursive(0,0,len(grid),len(grid[0]),None,'')

        return self.root