0427-建立四叉树

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 15:35:40 2023-09-13 15:35:40 Updated    

给你一个 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 。
![](https://assets.leetcode.com/uploads/2020/02/12/e1tree.png)

示例 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 个子网格，这样每个子网格都具有相同的值。
解释如下图所示：
![](https://assets.leetcode.com/uploads/2020/02/12/e2tree.png)

提示：

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

方法一：递归

思路与算法

我们可以使用递归的方法构建出四叉树。

具体地，我们用递归函数 dfs}(r_0, c_0, r_1, c_1)$ 处理给定的矩阵 grid 从 $r_0$ 行开始到 $r_1-1$ 行，从 $c_0$ 和 $c_1-1$ 列的部分。我们首先判定这一部分是否均为 $0$ 或 $1$，如果是，那么这一部分对应的是一个叶节点，我们构造出对应的叶节点并结束递归；如果不是，那么这一部分对应的是一个非叶节点，我们需要将其分成四个部分：行的分界线为 $\dfrac{r_0+r_1}{2，列的分界线为 $\dfrac{c_0+c_1}{2，根据这两条分界线递归地调用 dfs 函数得到四个部分对应的树，再将它们对应地挂在非叶节点的四个子节点上。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        def dfs(r0: int, c0: int, r1: int, c1: int) -> 'Node':
            if all(grid[i][j] == grid[r0][c0] for i in range(r0, r1) for j in range(c0, c1)):
                return Node(grid[r0][c0] == 1, True)
            return Node(
                True,
                False,
                dfs(r0, c0, (r0 + r1) // 2, (c0 + c1) // 2),
                dfs(r0, (c0 + c1) // 2, (r0 + r1) // 2, c1),
                dfs((r0 + r1) // 2, c0, r1, (c0 + c1) // 2),
                dfs((r0 + r1) // 2, (c0 + c1) // 2, r1, c1),
            )
        return dfs(0, 0, len(grid), len(grid))
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    Node *construct(vector<vector<int>> &grid) {
        function<Node*(int, int, int, int)> dfs = [&](int r0, int c0, int r1, int c1) {
            for (int i = r0; i < r1; ++i) {
                for (int j = c0; j < c1; ++j) {
                    if (grid[i][j] != grid[r0][c0]) { // 不是叶节点
                        return new Node(
                                true,
                                false,
                                dfs(r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),
                                dfs(r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),
                                dfs((r0 + r1) / 2, c0, r1, (c0 + c1) / 2),
                                dfs((r0 + r1) / 2, (c0 + c1) / 2, r1, c1)
                        );
                    }
                }
            }
            // 是叶节点
            return new Node(grid[r0][c0], true);
        };
        return dfs(0, 0, grid.size(), grid.size());
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public Node construct(int[][] grid) {
        return dfs(grid, 0, 0, grid.length, grid.length);
    }

    public Node dfs(int[][] grid, int r0, int c0, int r1, int c1) {
        boolean same = true;
        for (int i = r0; i < r1; ++i) {
            for (int j = c0; j < c1; ++j) {
                if (grid[i][j] != grid[r0][c0]) {
                    same = false;
                    break;
                }
            }
            if (!same) {
                break;
            }
        }

        if (same) {
            return new Node(grid[r0][c0] == 1, true);
        }

        Node ret = new Node(
            true,
            false,
            dfs(grid, r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),
            dfs(grid, r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),
            dfs(grid, (r0 + r1) / 2, c0, r1, (c0 + c1) / 2),
            dfs(grid, (r0 + r1) / 2, (c0 + c1) / 2, r1, c1)
        );
        return ret;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public Node Construct(int[][] grid) {
        return DFS(grid, 0, 0, grid.Length, grid.Length);
    }

    public Node DFS(int[][] grid, int r0, int c0, int r1, int c1) {
        bool same = true;
        for (int i = r0; i < r1; ++i) {
            for (int j = c0; j < c1; ++j) {
                if (grid[i][j] != grid[r0][c0]) {
                    same = false;
                    break;
                }
            }
            if (!same) {
                break;
            }
        }

        if (same) {
            return new Node(grid[r0][c0] == 1, true);
        }

        Node ret = new Node(
            true,
            false,
            DFS(grid, r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),
            DFS(grid, r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),
            DFS(grid, (r0 + r1) / 2, c0, r1, (c0 + c1) / 2),
            DFS(grid, (r0 + r1) / 2, (c0 + c1) / 2, r1, c1)
        );
        return ret;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func construct(grid [][]int) *Node {
    var dfs func([][]int, int, int) *Node
    dfs = func(rows [][]int, c0, c1 int) *Node {
        for _, row := range rows {
            for _, v := range row[c0:c1] {
                if v != rows[0][c0] { // 不是叶节点
                    rMid, cMid := len(rows)/2, (c0+c1)/2
                    return &Node{
                        true,
                        false,
                        dfs(rows[:rMid], c0, cMid),
                        dfs(rows[:rMid], cMid, c1),
                        dfs(rows[rMid:], c0, cMid),
                        dfs(rows[rMid:], cMid, c1),
                    }
                }
            }
        }
        // 是叶节点
        return &Node{Val: rows[0][c0] == 1, IsLeaf: true}
    }
    return dfs(grid, 0, len(grid))
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var construct = function(grid) {
    return dfs(grid, 0, 0, grid.length, grid.length);
};

const dfs = (grid, r0, c0, r1, c1) => {
    let same = true;
    for (let i = r0; i < r1; ++i) {
        for (let j = c0; j < c1; ++j) {
            if (grid[i][j] !== grid[r0][c0]) {
                same = false;
                break;
            }
        }
        if (!same) {
            break;
        }
    }

    if (same) {
        return new Node(grid[r0][c0] === 1, true);
    }

    const ret = new Node(
        true,
        false,
        dfs(grid, r0, c0, Math.floor((r0 + r1) / 2), Math.floor((c0 + c1) / 2)),
        dfs(grid, r0, Math.floor((c0 + c1) / 2), Math.floor((r0 + r1) / 2), c1),
        dfs(grid, Math.floor((r0 + r1) / 2), c0, r1, Math.floor((c0 + c1) / 2)),
        dfs(grid, Math.floor((r0 + r1) / 2), Math.floor((c0 + c1) / 2), r1, c1)
    );
    return ret;
}

复杂度分析

  • 时间复杂度：$O(n^2 \log n)$。这里给出一个较为宽松的时间复杂度上界。记 $T(n)$ 为边长为 $n$ 的数组需要的时间复杂度，那么「判定这一部分是否均为 $0$ 或 $1$」需要的时间为 $O(n^2)$，在这之后会递归调用 $4$ 规模为 $n/2$ 的子问题，那么有：

    $$
    T(n) = 4T(n/2) + O(n^2)
    $$

    以及：

    $$
    T(1) = O(1)
    $$

    根据主定理，可以得到 $T(n) = O(n^2 \log n)$。但如果判定需要的时间达到了渐近紧界 $\Theta(n^2)$，那么说明这一部分包含的元素大部分都是相同的，也就是说，有很大概率在深入递归时遇到元素完全相同的一部分，从而提前结束递归。因此 $O(n^2 \log n)$ 的时间复杂度是很宽松的，实际运行过程中可以跑出与方法二 $O(n^2)$ 时间复杂度代码相似的速度。

  • 空间复杂度：$O(\log n)$，即为递归需要使用的栈空间。

方法二：递归 + 二维前缀和优化

思路与算法

我们可以对方法一中暴力判定某一部分是否均为 $0$ 或 $1$ 的代码进行优化。

具体地，当某一部分均为 $0$ 时，它的和为 $0$；某一部分均为 $1$ 时，它的和为这一部分的面积大小。因此我们可以使用二维前缀和（参考「304. 二维区域和检索 - 矩阵不可变」 ）进行优化。我们可以与处理出数组 grid 的二维前缀和，这样一来，当我们需要判定某一部分是否均为 $0$ 或 $1$ 时，可以在 $O(1)$ 的时间内得到这一部分的和，从而快速地进行判断。

代码

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        n = len(grid)
        pre = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i - 1][j - 1]

        def getSum(r0: int, c0: int, r1: int, c1: int) -> int:
            return pre[r1][c1] - pre[r1][c0] - pre[r0][c1] + pre[r0][c0]

        def dfs(r0: int, c0: int, r1: int, c1: int) -> 'Node':
            total = getSum(r0, c0, r1, c1)
            if total == 0:
                return Node(False, True)
            if total == (r1 - r0) * (c1 - c0):
                return Node(True, True)
            return Node(
                True,
                False,
                dfs(r0, c0, (r0 + r1) // 2, (c0 + c1) // 2),
                dfs(r0, (c0 + c1) // 2, (r0 + r1) // 2, c1),
                dfs((r0 + r1) // 2, c0, r1, (c0 + c1) // 2),
                dfs((r0 + r1) // 2, (c0 + c1) // 2, r1, c1),
            )

        return dfs(0, 0, n, n)
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    Node *construct(vector<vector<int>> &grid) {
        int n = grid.size();
        vector<vector<int>> pre(n + 1, vector<int>(n + 1));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i - 1][j - 1];
            }
        }

        auto getSum = [&](int r0, int c0, int r1, int c1) {
            return pre[r1][c1] - pre[r1][c0] - pre[r0][c1] + pre[r0][c0];
        };

        function<Node *(int, int, int, int)> dfs = [&](int r0, int c0, int r1, int c1) {
            int total = getSum(r0, c0, r1, c1);
            if (total == 0) {
                return new Node(false, true);
            }
            if (total == (r1 - r0) * (c1 - c0)) {
                return new Node(true, true);
            }
            return new Node(
                    true,
                    false,
                    dfs(r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),
                    dfs(r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),
                    dfs((r0 + r1) / 2, c0, r1, (c0 + c1) / 2),
                    dfs((r0 + r1) / 2, (c0 + c1) / 2, r1, c1)
            );
        };

        return dfs(0, 0, n, n);
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public Node construct(int[][] grid) {
        int n = grid.length;
        int[][] pre = new int[n + 1][n + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i - 1][j - 1];
            }
        }
        return dfs(grid, pre, 0, 0, n, n);
    }

    public Node dfs(int[][] grid, int[][] pre, int r0, int c0, int r1, int c1) {
        int total = getSum(pre, r0, c0, r1, c1);
        if (total == 0) {
            return new Node(false, true);
        } else if (total == (r1 - r0) * (c1 - c0)) {
            return new Node(true, true);
        }

        Node ret = new Node(
            true,
            false,
            dfs(grid, pre, r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),
            dfs(grid, pre, r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),
            dfs(grid, pre, (r0 + r1) / 2, c0, r1, (c0 + c1) / 2),
            dfs(grid, pre, (r0 + r1) / 2, (c0 + c1) / 2, r1, c1)
        );
        return ret;
    }

    public int getSum(int[][] pre, int r0, int c0, int r1, int c1) {
        return pre[r1][c1] - pre[r1][c0] - pre[r0][c1] + pre[r0][c0];
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    public Node Construct(int[][] grid) {
        int n = grid.Length;
        int[][] pre = new int[n + 1][];
        for (int i = 0; i <= n; ++i) {
            pre[i] = new int[n + 1];
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i - 1][j - 1];
            }
        }
        return DFS(grid, pre, 0, 0, n, n);
    }

    public Node DFS(int[][] grid, int[][] pre, int r0, int c0, int r1, int c1) {
        int total = GetSum(pre, r0, c0, r1, c1);
        if (total == 0) {
            return new Node(false, true);
        } else if (total == (r1 - r0) * (c1 - c0)) {
            return new Node(true, true);
        }

        Node ret = new Node(
            true,
            false,
            DFS(grid, pre, r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),
            DFS(grid, pre, r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),
            DFS(grid, pre, (r0 + r1) / 2, c0, r1, (c0 + c1) / 2),
            DFS(grid, pre, (r0 + r1) / 2, (c0 + c1) / 2, r1, c1)
        );
        return ret;
    }

    public int GetSum(int[][] pre, int r0, int c0, int r1, int c1) {
        return pre[r1][c1] - pre[r1][c0] - pre[r0][c1] + pre[r0][c0];
    }
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func construct(grid [][]int) *Node {
    n := len(grid)
    pre := make([][]int, n+1)
    pre[0] = make([]int, n+1)
    for i, row := range grid {
        pre[i+1] = make([]int, n+1)
        for j, v := range row {
            pre[i+1][j+1] = pre[i+1][j] + pre[i][j+1] - pre[i][j] + v
        }
    }

    var dfs func(r0, c0, r1, c1 int) *Node
    dfs = func(r0, c0, r1, c1 int) *Node {
        total := pre[r1][c1] - pre[r1][c0] - pre[r0][c1] + pre[r0][c0]
        if total == 0 {
            return &Node{Val: false, IsLeaf: true}
        }
        if total == (r1-r0)*(c1-c0) {
            return &Node{Val: true, IsLeaf: true}
        }
        rMid, cMid := (r0+r1)/2, (c0+c1)/2
        return &Node{
            true,
            false,
            dfs(r0, c0, rMid, cMid),
            dfs(r0, cMid, rMid, c1),
            dfs(rMid, c0, r1, cMid),
            dfs(rMid, cMid, r1, c1),
        }
    }
    return dfs(0, 0, n, n)
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var construct = function(grid) {
    const n = grid.length;
    const pre = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= n; ++i) {
        for (let j = 1; j <= n; ++j) {
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i - 1][j - 1];
        }
    }
    return dfs(grid, pre, 0, 0, n, n);
};

const dfs = (grid, pre, r0, c0, r1, c1) => {
    const total = getSum(pre, r0, c0, r1, c1);
    if (total === 0) {
        return new Node(false, true);
    } else if (total === (r1 - r0) * (c1 - c0)) {
        return new Node(true, true);
    }

    const ret = new Node(
        true,
        false,
        dfs(grid, pre, r0, c0, Math.floor((r0 + r1) / 2), Math.floor((c0 + c1) / 2)),
        dfs(grid, pre, r0, Math.floor((c0 + c1) / 2), Math.floor((r0 + r1) / 2), c1),
        dfs(grid, pre, Math.floor((r0 + r1) / 2), c0, r1, Math.floor((c0 + c1) / 2)),
        dfs(grid, pre, Math.floor((r0 + r1) / 2), Math.floor((c0 + c1) / 2), r1, c1)
    );
    return ret;
}

const getSum = (pre, r0, c0, r1, c1) => {
    return pre[r1][c1] - pre[r1][c0] - pre[r0][c1] + pre[r0][c0];
}

复杂度分析

  • 时间复杂度：$O(n^2)$。在最坏情况下，数组 grid 中交替出现 $0$ 和 $1$，此时每一个叶节点对应着 $1 \times 1$ 的区域。记 $T(n)$ 为边长为 $n$ 的数组需要的时间复杂度，那么有：

    $$
    T(n) = 4T(n/2) + O(1)
    $$

    以及：

    $$
    T(1) = O(1)
    $$

    根据主定理，可以得到 $T(n) = O(n^2)$。预处理二维前缀和需要的时间也为 $O(n^2)$，因此总时间复杂度为 $O(n^2)$。

  • 空间复杂度：$O(n^2)$，即为二维前缀和需要使用的空间。

 Comments
On this page
0427-建立四叉树