大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

题目很长，但是不要害怕。

题目所说的四分树，其实就是用来表示矩阵数据的一种数据结构。

把一个边长为 2 的幂的正方形均分成 4 块，然后再均分到不能均分为止即为叶子节点。

树的节点分成两种：一种是叶子节点（矩阵内所有的取值一样），一种不是叶子节点（矩阵内的取值不一样，需要继续细分）。

具体地建立四叉树的过程，可以参考我画的图进行理解：

解题方法

首先，这种结构就是「树」，肯定使用递归求解。重要的是如何判断此树结构如何判断叶子节点、val。

所以定义了一个新的函数isQuadTree：

  • 如果一个正方形中所有的数字都是 427. 建立四叉树 - 图1，则 val 是 True；
  • 如果一个正方形中所有的数字都是 427. 建立四叉树 - 图2，则 val 是 False。
  • 否则，说明格子里的值不都是相同的，返回 None.

判断 leaf 的方法是看看格子里的所有的值是不是相同的，如果全是 427. 建立四叉树 - 图3或者 427. 建立四叉树 - 图4那么就是 leaf，否则就不是 leaf。

其他的难点就在把正方形进行切分成四块了，这个不是难点。

  1. """
  2. # Definition for a QuadTree node.
  3. class Node:
  4.     def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
  5.         self.val = val
  6.         self.isLeaf = isLeaf
  7.         self.topLeft = topLeft
  8.         self.topRight = topRight
  9.         self.bottomLeft = bottomLeft
  10.         self.bottomRight = bottomRight
  11. """
  12. class Solution:
  13.     def construct(self, grid):
  14.         """
  15.         :type grid: List[List[int]]
  16.         :rtype: Node
  17.         """
  18.         isLeaf = self.isQuadTree(grid)
  19.         _len = len(grid)
  20.         if isLeaf == None:
  21.             mid = _len // 2
  22.             topLeftGrid = [[grid[i][j] for j in range(mid)] for i in range(mid)]
  23.             topRightGrid = [[grid[i][j] for j in range(mid, _len)] for i in range(mid)]
  24.             bottomLeftGrid = [[grid[i][j] for j in range(mid)] for i in range(mid, _len)]
  25.             bottomRightGrid = [[grid[i][j] for j in range(mid, _len)] for i in range(mid, _len)]
  26.             node = Node(True, False, self.construct(topLeftGrid), self.construct(topRightGrid), 
  27.                         self.construct(bottomLeftGrid), self.construct(bottomRightGrid))
  28.         elif isLeaf == False:
  29.             node = Node(False, True, None, None, None, None)
  30.         else:
  31.             node = Node(True, True, None, None, None, None)
  32.         return node
  34.     def isQuadTree(self, grid):
  35.         _len = len(grid)
  36.         _sum = 0
  37.         for i in range(_len):
  38.             _sum += sum(grid[i])
  39.         if _sum == _len ** 2:
  40.             return True
  41.         elif _sum == 0:
  42.             return False
  43.         else:
  44.             return None

总结

  1. 重点是理解题意！递归并不难。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。