LeetCode 427：Construct Quad Tree 题解与两种思路对比
LeetCode 427 要求：给定一个只包含 0 和 1 的 n×n 矩阵 grid，用四叉树来表示这个矩阵，并返回四叉树的根节点。 四叉树中每个内部节点恰好有 4 个子节点（左上、右上、左下、右下），每个节点包含两个关键属性：val 和 isLeaf。leetcode
val：如果该节点表示的区域全是 1，则为 True；如果全是 0，则为 False；当 isLeaf == False 时，val 取 True/False 都行，不影响答案。leetcode
isLeaf：如果该节点是叶子节点（没有子节点），为 True；如果有四个子节点，为 False。leetcode
题目给出的构造规则是标准的递归划分流程：如果当前区域所有值相同，就把它变成一个叶子节点；否则把区域划分成四个等大的子区域，分别递归构建四个子树。algo+1
方法一：自顶向下的经典 Divide & Conquer
大部分官方/题解网站推荐的写法，都是自顶向下 + Divide & Conquer。sparkcodehub+2
核心思路：
- 针对当前子矩形（比如用左上角坐标和边长来表示），先扫描这一块区域，判断是否「全 0」或「全 1」。
- 如果是「全相同」，直接构造一个叶子节点
isLeaf = true, val = 0/1，返回。 - 否则，把这块区域按照中点分成四个等大子区域：topLeft、topRight、bottomLeft、bottomRight，各自递归构造子树。
- 返回一个内部节点
isLeaf = false，四个子节点挂在对应指针上即可。sparkcodehub+1
这个方案直接体现了Divide & Conquer的三个步骤：wikipedia+1
- Divide：把当前子矩形拆成四个象限。
- Conquer：递归构造四棵子树。
- Combine：用这四棵子树组装出当前节点（内部节点或叶子节点）。
很多时候大家会以为「Divide & Conquer 就是先分到不能再分，然后在合并阶段做大量工作」，比如归并排序的感觉。 实际上，教科书定义只要求「拆成子问题 → 递归求解 → 用子问题的解得到原问题解」，Combine 这一步可以非常轻，比如这里就只是构造一个节点并挂四个子指针而已。scaler+2
自顶向下的复杂度和优化点
复杂度方面，常见题解一般认为总时间复杂度为 O(n²) 或 O(n² log n) 量级，主要原因是每一层总共访问的格子数是 O(n²)，而树的高度是 log n 级别。youtubealgo+1
真正的优势在于：对于很多「大块区域本来就全 0 或全 1」的情况，自顶向下在很高的层级就直接返回叶子了，不会再把它拆成很多 1×1 小块，递归深度和节点数都大幅减少。algo+1
所以，自顶向下先判断统一性再分割，既是标准的 Divide & Conquer，也往往更贴近四叉树实际应用中的「自适应划分」风格。pratikpandey.substack+1
方法二：自底向上的「先分到底，再向上 merge」
你的思路是另一种非常自然的写法，可以概括为：「先把区域一直劈到 1×1，再在回溯阶段尝试合并成更大的叶子」。这也是一种 Divide & Conquer，只是 Combine 做得更"重"一些。neetcode+1
具体步骤：
- 递归时按横纵对半分割当前区域，直到子区域变成 1×1 小格子。
- 到 1×1 时，直接用该格子的值构造一个叶子节点，
isLeaf = true, val = grid[i][j]，返回。 - 回溯到上一层时，拿到四个子节点，进入merge 逻辑：
- 如果四个子节点都是叶子，且它们的 val 完全相同，那么可以「合并」成一个更大的叶子节点：创建一个新叶子节点，值为这个统一的 0/1，释放或丢弃四个小叶子，返回这个新的大叶子节点。
- 否则，说明这块区域不是 uniform，就构造一个内部节点：
isLeaf = false，val 随便设（通常设为 false），把四个子节点挂上去，返回这个内部节点。vultr+1
只要保证合并条件写对：
- 四个子节点必须都是叶子；
- 四个子节点的 val 完全一样；
这个办法与自顶向下的最终树结构是等价的。vultr+1
两种思路的对比与选择
从算法范式上看，两种写法都符合Divide & Conquer，只是拆分和合并的侧重点不同。wikipedia+1
| 维度 | 自底向上：先分到底再 merge | 自顶向下：先判 uniform 再分 |
|---|---|---|
| 递归过程 | 一路拆到 1×1，再在回溯中判断四叶子能否合并sparkcodehub | 先看当前块是否 uniform，非 uniform 才继续拆algo |
| Combine 工作量 | merge 阶段稍重，需要检查 4 个子节点是否都叶子且同值sparkcodehub | Combine 很轻，大多只是 new 一个父节点algo |
| uniform 区域处理 | 必须先拆到最小单位再往上合并 | 可能在高层就直接变成叶子，不再继续拆algo+1 |
| 实际推荐程度 | 思路完全正确，可 AC，写法稍微"工程化"一点 | 编辑器官方解、NeetCode 等主流题解更偏向此写法algo+2 |
从面试/刷题角度看：
- 你的方案：非常适合作为「先凭直觉写一个可以工作的版本」，逻辑直接，特别像很多自底向上的 DP。
- 官方方案：更贴近四叉树的直观定义（当前区域 uniform 就是叶子），也更接近实际工程里构建四叉树的常见方式，因此一般题解、视频教程都会用这一版。grandyang+2
关于 Divide & Conquer、Top-down 和 Bottom-up 的理解
最后回到你问的那个哲学问题：「自顶向下是不是就不符合 Divide & Conquer？Divide & Conquer 不是要先 split 到不能再 split，然后 merge 吗？」
**Divide & Conquer 的定义只是「拆成子问题 → 递归解决 → 组合答案」，没有规定合并一定发生在"最后一层"。**scaler+1
自顶向下 quad tree 构造完全是 Divide & Conquer：在每个节点，要么「不用再分，直接得解」（叶子），要么「拆成 4 个子问题，把 4 个解合起来」；只是合并操作比较轻，不像归并排序那样巨大的 merge 阶段。youtubealgo
你的写法则更偏「Bottom-up」，也同样是 Divide & Conquer，只不过把大量工作放到回溯时的 merge 阶段来做。neetcode+1
如果写成一行总结：
自顶向下 + uniform 检查是更"教科书式"的 Divide & Conquer；自底向下再 merge 是更"工程化"的 Divide & Conquer，两者同属一个范式，只是结构分布不同。algo+2
实际刷题中，两种写法都可以放心用，你现在这套自底向上的思路逻辑是完全正确的，只要小心合并条件即可。