【面试经典 150 | 分治】建立四叉树

本文主要是介绍【面试经典 150 | 分治】建立四叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：递归
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【四叉树】【分治】

题目来源

427. 建立四叉树

解题思路

本题参考官方题解。

方法一：递归

思路

我们可以递归的构建出四叉树。

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

代码

/*
// Definition for a QuadTree node.
class Node {
public:bool val;bool isLeaf;Node* topLeft;Node* topRight;Node* bottomLeft;Node* bottomRight;Node() {val = false;isLeaf = false;topLeft = NULL;topRight = NULL;bottomLeft = NULL;bottomRight = NULL;}Node(bool _val, bool _isLeaf) {val = _val;isLeaf = _isLeaf;topLeft = NULL;topRight = NULL;bottomLeft = NULL;bottomRight = NULL;}Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {val = _val;isLeaf = _isLeaf;topLeft = _topLeft;topRight = _topRight;bottomLeft = _bottomLeft;bottomRight = _bottomRight;}
};
*/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());}
};

复杂度分析

时间复杂度： $O(n^2logn)$ ，见分析.