1 QuadTree Structure

Read a 2D array image, buid a quad tree. 输入的矩阵如下：

[[1, 1, 0, 0],
 [1, 1, 0, 0],
 [1, 0, 1, 1],
 [1, 1, 1, 1]]

然后build出来的quadtree的root的child, 左上角应该是1， 右上是0，左下是2，右下是1

class Node(object):
    def __init__(self, val=None):
        self.val = val
        #[NW, NE, SE, SW]
        self.chidren = [None]*4

class Solution(object):
    def QuadTree(self, image):
        if not image or not image[0]:
            return
        i, j = (0,0), (len(image)-1,len(image[0])-1)
        root = self.build(i, j, image)
        return root

    def build(self, i, j, image):
        if i==j:
            return Node(image[i[0]][i[1]])

        root = Node()
        rmid = (i[0]+j[0])//2
        cmid = (i[1]+j[1])//2
        NW = self.build(i, (rmid, cmid), image)
        NE = self.build((i[0],cmid+1), (rmid, j[1]), image)
        SE = self.build((rmid+1, cmid+1), j, image)
        SW = self.build((rmid+1, i[1]),(j[0],cmid), image)

        #print i, (rmid, cmid), NW.val
        if (NW.val,NE.val,SE.val,SW.val) == (0,0,0,0):
            root.val = 0
        elif (NW.val,NE.val,SE.val,SW.val) == (1,1,1,1):
            root.val = 1
        else:
            root.val = 2
            root.chidren = [NW,NE,SE,SW]

        return root

image = [
[1, 1, 0, 0],
[1, 1, 0, 0],
[1, 0, 1, 1],
[1, 1, 1, 1]]

so = Solution()
root = so.QuadTree(image)
print root.val
print [c.val for c in root.chidren]