427. 建立四叉树

🟠   🔖  树 数组 分治 矩阵  🔗 力扣 LeetCode

题目

Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree.

Return the root of the Quad-Tree representinggrid.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

• val: True if the node represents a grid of 1's or False if the node represents a grid of 0's. Notice that you can assign the val to True or False when isLeaf is False, and both are accepted in the answer.
• isLeaf: True if the node is a leaf node on the tree or False if the node has four children.

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

We can construct a Quad-Tree from a two-dimensional area using the following steps:

1. If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
2. If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
3. Recurse for each of the children with the proper sub-grid.

If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

You don't need to read this section for solving the problem. This is only if you want to understand the output format here. The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.

Example 1:

Input: grid = [[0,1],[1,0]]

Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]

Explanation: The explanation of this example is shown below:

Notice that 0 represents False and 1 represents True in the photo representing the Quad-Tree.

Example 2:

Input: grid = [[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]]

Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.

The topLeft, bottomLeft and bottomRight each has the same value.

The topRight have different values so we divide it into 4 sub-grids where each has the same value.

Explanation is shown in the photo below:

Constraints:

• n == grid.length == grid[i].length
• n == 2^x where 0 <= x <= 6

题目大意

给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

你需要返回能表示矩阵 grid 的 四叉树 的根结点。

四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：

• val：储存叶子结点所代表的区域的值。1 对应 True ，0 对应 False 。注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
• isLeaf: 当这个节点是一个叶子结点时为 True ，如果它有 4 个子节点则为 False 。

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

我们可以按以下步骤为二维区域构建四叉树：

1. 如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
2. 如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
3. 使用适当的子网格递归每个子节点。

如果你想了解更多关于四叉树的内容，可以参考 wiki 。

四叉树格式：

你不需要阅读本节来解决这个问题。只有当你想了解输出格式时才会这样做。输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。

它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。

如果 isLeaf 或者 val 的值为 True ，则表示它在列表 [isLeaf, val] 中的值为 1 ；如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。

示例 1：

输入： grid = [[0,1],[1,0]]

输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]

解释： 此示例的解释如下：

请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。

示例 2：

输入： grid = [[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]]

输出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

解释： 网格中的所有值都不相同。我们将网格划分为四个子网格。

topLeft，bottomLeft 和 bottomRight 均具有相同的值。

topRight 具有不同的值，因此我们将其再分为 4 个子网格，这样每个子网格都具有相同的值。

解释如下图所示：

提示：

1. n == grid.length == grid[i].length
2. n == 2^x 其中 0 <= x <= 6

解题思路

这个问题本质上是一个递归划分问题，类似于分治算法。需要不断地将网格划分为四个子网格，直到找到一个可以用叶子节点来表示的区域。

1. 每个节点要么是叶子节点，要么是内部节点：

   • 如果是叶子节点，它将包含子网格的单一值（0 或 1）；
   • 如果是内部节点，它将有四个指针指向子节点。

2. 递归地构建四叉树：

   • 如果当前网格是同一个值（即所有单元格都为 0 或都为 1），则构造一个叶子节点。
   • 否则，对当前网格的四个子区域（左上、右上、左下、右下）分别递归构造子节点。

3. 终止条件：

   • 当网格区域缩小到只有一个单元格时，直接返回该单元格的值作为叶子节点。
   • 当所有单元格的值相同，可以创建一个叶子节点。

复杂度分析

• 时间复杂度: O(n^2 * log n)，其中 n 是 grid 的边长。需要递归地划分网格并检查每个子网格的值。由于网格划分的方式类似于四叉树，每次递归将网格的大小减半。
• 空间复杂度: O(log n)，因为递归栈的深度与网格大小呈对数关系。

代码

/**
 * // Definition for a QuadTree node.
 * function _Node(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight) {
 *    this.val = val;
 *    this.isLeaf = isLeaf;
 *    this.topLeft = topLeft;
 *    this.topRight = topRight;
 *    this.bottomLeft = bottomLeft;
 *    this.bottomRight = bottomRight;
 * };
 */

/**
 * @param {number[][]} grid
 * @return {_Node}
 */
var construct = function (grid) {
	const buildTree = (rowStart, rowEnd, colStart, colEnd) => {
		let first = grid[rowStart][colStart],
			isLeaf = true;
		out: for (let i = rowStart; i < rowEnd; i++) {
			for (let j = colStart; j < colEnd; j++) {
				if (grid[i][j] !== first) {
					isLeaf = false;
					break out;
				}
			}
		}

		if (isLeaf) {
			return new Node(first == 1, true, null, null, null, null);
		} else {
			const rowMid = ((rowStart + rowEnd) / 2) | 0;
			const colMid = ((colStart + colEnd) / 2) | 0;
			return new Node(
				true,
				false,
				buildTree(rowStart, rowMid, colStart, colMid), // top-left
				buildTree(rowStart, rowMid, colMid, colEnd), // top-right
				buildTree(rowMid, rowEnd, colStart, colMid), // bottom-left
				buildTree(rowMid, rowEnd, colMid, colEnd) // bottom-right
			);
		}
	};
	const n = grid.length;
	return buildTree(0, n, 0, n);
};