@@ -0,0 +1,2468 @@
+# Time:  O(n)%0A# Space: O(h)%0A%0A# We want to use quad trees to store an N x N boolean grid.%0A# Each cell in the grid can only be true or false.%0A# The root node represents the whole grid. For each node,%0A# it will be subdivided into four children nodes until the values%0A# in the region it represents are all the same.%0A#%0A# Each node has another two boolean attributes : isLeaf and val. isLeaf is true%0A# if and only if the node is a leaf node.%0A# The val attribute for a leaf node contains the value of the region it represents.%0A#%0A# Your task is to use a quad tree to represent a given grid.%0A# The following example may help you understand the problem better:%0A#%0A# Given the 8 x 8 grid below, we want to construct the corresponding quad tree:%0A# It can be divided according to the definition above:%0A#%0A# The corresponding quad tree should be as following,%0A# where each node is represented as a (isLeaf, val) pair.%0A#%0A# For the non-leaf nodes, val can be arbitrary, so it is represented as *.%0A#%0A# Note:%0A# - N is less than 1000 and guaranteened to be a power of 2.%0A# - If you want to know more about the quad tree, you can refer to its wiki.%0A%0A# Definition for a QuadTree node.%0Aclass Node(object):%0A    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):%0A        self.val = val%0A        self.isLeaf = isLeaf%0A        self.topLeft = topLeft%0A        self.topRight = topRight%0A        self.bottomLeft = bottomLeft%0A        self.bottomRight = bottomRight%0A%0A%0Aclass Solution(object):%0A    def construct(self, grid):%0A        %22%22%22%0A        :type grid: List%5BList%5Bint%5D%5D%0A        :rtype: Node%0A        %22%22%22%0A        def dfs(grid, x, y, l):%0A            if l == 1:%0A                return Node(grid%5Bx%5D%5By%5D == 1, True, None, None, None, None)%0A            half = l // 2%0A            topLeftNode = dfs(grid, x, y, half)%0A            topRightNode = dfs(grid, x, y+half, half)%0A            bottomLeftNode = dfs(grid, x+half, y, half)%0A            bottomRightNode = dfs(grid, x+half, y+half, half)%0A            if topLeftNode.isLeaf and topRightNode.isLeaf and %5C%0A               bottomLeftNode.isLeaf and bottomRightNode.isLeaf and %5C%0A               topLeftNode.val == topRightNode.val == bottomLeftNode.val == bottomRightNode.val:%0A                return Node(topLeftNode.val, True, None, None, None, None)%0A            return Node(True, False, topLeftNode, topRightNode, bottomLeftNode, bottomRightNode)%0A        %0A        if not grid:%0A            return None%0A        return dfs(grid, 0, 0, len(grid))%0A

Create construct-quad-tree.py