题目

难度：★★★☆☆
类型：二叉树

我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。网络中每一格的值只会是真或假。树的根结点代表整个网络。对于每个结点, 它将被分等成四个孩子结点直到这个区域内的值都是相同的.

每个结点还有另外两个布尔变量: isLeaf 和 val。isLeaf 当这个节点是一个叶子结点时为真。val 变量储存叶子结点所代表的区域的值。

你的任务是使用一个四叉树表示给定的网络。下面的例子将有助于你理解这个问题：

给定下面这个8 x 8 网络，我们将这样建立一个对应的四叉树：

我们要用四叉树表示这样一个棋盘

由上文的定义，它能被这样分割：

上述棋盘的分割方式

对应的四叉树应该像下面这样，每个结点由一对 (isLeaf, val) 所代表.

对于非叶子结点，val 可以是任意的，所以使用 * 代替。

可以表示上述棋盘的四叉树

提示

N 将小于 1000 且确保是 2 的整次幂。
如果你想了解更多关于四叉树的知识，你可以参考这个 wiki 页面。

解答

题目中四叉树的构建是为了表示一个布尔方阵，我们的构建遵循构建法则，我们定义一个构建函数，实现构建指定区域四叉树的功能，通过递归调用本函数实现所有四叉树结点的构建。这里重点介绍使用函数递归调用实现四叉树构建的思路：

1. 函数的功能

实现指定范围的四叉树构建。

2. 函数的输入和输出

我们设计的四叉树，需要只需要输入要构建网格中四叉树的网格即可。不过我们这里为了便于递归，把整个网格作为每次递归函数的输入，并且指定要构建四叉树的范围，这里的范围用左上角坐标和区域边长来表示。

函数的输出是根据指定网格构建而成的四叉树，换句话说，这个四叉树是输入网格的唯一表示。

3. 函数的实现

计算所考察正方形区域中元素的纯度，这里通过计数方式实现，如果区域内所有数字均为零或一，表明该区域满足构建叶子结点的条件，直接返回对应的叶子结点即可。
如果所考察的正方形区域中既有零又有1，我们就需要把它当做普通结点进行对待，实例化一个结点，并且把四个子树挂在这个结点上，设当前区域左上角坐标为（h, w），当前区域边长为N，边长的一半为n，那么四个子树所表示的区域分别为：
（1）左上子树表示的区域，左上角为(h, w)，边长为n；
（2）右上子树表示的区域，左上角为(h, w+n)，边长为n；
（3）左下子树表示的区域，左上角为(h+n, w)，边长为n；
（4）右下子树表示的区域，左上角为(h+n, w+n)，边长为n。
有了区域，通过调用本函数可以实现四个子树的构建，通过递归可以实现整个四叉树的构建。

# Definition for a QuadTree node.
class Node:
    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:
    def construct(self, grid):
        def dfs(grid, h, w, N):
            """
            用于构建方格([h, w], [h+N, w+N])的四叉树
            :param grid: 输入网格
            :param h: 方格左上角纵坐标
            :param w: 方格左上角横坐标
            :param N: 方格边长
            :return: 返回一棵构建好的四叉树
            """

            total = sum([grid[h+i][w+j] for i in range(N) for j in range(N)])   # 求取当前方格内的和

            if total == 0:                                              # 如果方格内所有元素都是0
                return Node(False, True, None, None, None, None)        # 构造一个值为False的叶子节点

            elif total == N * N:                                        # 如果方格内所有元素都是1
                return Node(True, True, None, None, None, None)         # 构造一个值为True的叶子节点

            else:                                                       # 说明方格内有0有1
                root = Node('*', False, None, None, None, None)         # 构造一个值为"*"的中间结点
                n = N // 2                                              # 求方格的一半
                root.topLeft = dfs(grid, h, w, n)                       # 构建左上子树
                root.topRight = dfs(grid, h, w+n, n)                    # 构建右上子树
                root.bottomLeft = dfs(grid, h+n, w, n)                  # 构建左下子树
                root.bottomRight = dfs(grid, h+n, w+n, n)               # 构建右下子树
                return root                                             # 返回构建完成的树

        return dfs(grid, 0, 0, len(grid))


if __name__ == "__main__":
    s = Solution()
    print(s.construct([[1, 1, 1, 1, 0, 0, 0, 0],
                       [1, 1, 1, 1, 0, 0, 0, 0],
                       [1, 1, 1, 1, 1, 1, 1, 1],
                       [1, 1, 1, 1, 1, 1, 1, 1],
                       [1, 1, 1, 1, 0, 0, 0, 0],
                       [1, 1, 1, 1, 0, 0, 0, 0],
                       [1, 1, 1, 1, 0, 0, 0, 0],
                       [1, 1, 1, 1, 0, 0, 0, 0],
                       ]))

如有疑问或建议，欢迎评论区留言~

427. 建立四叉树（Python）

427. 建立四叉树（Python）

题目

提示

解答