Leetcode 427. Construct Quad Tree

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

**解析：**采用递归的方法构建Quad Tree，逐步分解即可。

• Version 1

""" # Definition for a QuadTree node. class Node:def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):self.val = valself.isLeaf = isLeafself.topLeft = topLeftself.topRight = topRightself.bottomLeft = bottomLeftself.bottomRight = bottomRight """class Solution:def construct(self, grid: List[List[int]]) -> 'Node':return self.quadTree(grid, 0, 0, len(grid))def quadTree(self, grid, row_start, column_start, n):total = 0node = Node()for i in range(row_start, row_start + n):total += sum(grid[i][column_start:column_start+n])if total == 0:node.isLeaf = 1node.val = 0elif total == n * n:node.isLeaf = 1node.val = 1else:node.isLeaf = 0node.val = 1node.topLeft = self.quadTree(grid, row_start, column_start, n // 2)node.topRight = self.quadTree(grid, row_start, column_start + n // 2, n // 2)node.bottomLeft = self.quadTree(grid, row_start + n // 2, column_start, n // 2)node.bottomRight = self.quadTree(grid, row_start + n // 2, column_start + n // 2, n // 2)return node

Reference

1. https://leetcode.com/problems/construct-quad-tree/