题目描述
思路解析
一句话答案：LeetCode 558 两个四叉树的逻辑或：两个 n×n 矩阵按位或后仍用四叉树表示，靠递归四象限加叶子短路——全 1 返全 1、全 0 返另一棵，四子同值合并成叶，时间 O(n²)。
两棵四叉树按位或，要还回什么
给两棵四叉树，各表示一个 n×n 的 0/1 矩阵，请返回它们按位逻辑或后的矩阵，仍用四叉树表示；按位或就是对应位置只要有一个 1，那格就是 1。四叉树的节点要么是叶子，也就是 isLeaf 为真、整块同一个值 val 记 0 或 1，要么带四个孩子分管四个象限。题名有处译作交集，但按代码和 slug 算的是逻辑或、也就是两块并集，别被译名带偏。
先摊平成矩阵再逐格或，卡在哪
把两棵树各自还原成矩阵、逐格或、再压回四叉树，也能出答案，但硬把树摊平，四叉树最值钱的分块结构全丢了：一个叶子本可罩着一大片同色区域，摊平却逼你把里面每格都单独或一遍，n 一大就是 n² 格的白工。
叶子一出现，整块就能定案
省力气的口子在叶子上。只要比的两块有一块是叶子，这象限当场能定，不必再拆。手里是全 1 叶子，1 或任何都是 1，结果必是全 1，直接返回全 1 叶子，对面看都不看；手里是全 0 叶子，0 或 x 等于 x，结果全看对方，就把另一棵子树原样返回。两块都不是叶子、谁也短路不了，才真往下拆。
四个象限各算各的，何时并回一块
两块都不是叶子时，把它们对齐拆开，对 topLeft、topRight、bottomLeft、bottomRight 四象限分别递归求或，各拿回一个子结果。凑齐后再问：四个是不是又拼成一整块纯色？判据是四个都是叶子且 val 全相等——这时底下这层结构多余，合并成一个叶子往上返，就是同值合并。只要有一个还是内部节点，或四个叶子值不齐，这块就不纯，只能新建内部节点、把四子挂上去返回。
拿一组 4×4 的 A、B 演算一遍
看一组 4×4 的例子。A 左上是全 1 叶子、右上是全 0 叶子，左下、右下两块不纯；B 右上是全 1 叶子，其余三块不纯。两棵根都不是叶子，对四象限分别递归。
左上，A 是全 1 叶子，短路第一种，直接返回全 1 叶子，B 的左上不必看。右上，A 是全 0 叶子，短路第二种，返回另一棵，即 B 的右上全 1 叶子，照搬成全 1。左下两边都不纯，拆四小格，四格分别是 1 或 0、0 或 1、0 或 1、1 或 0，全得 1，四个同值叶子合并，并回全 1 叶子。右下同样拆四格，得 1、1、0、1，不齐，合并不成，只能保留成内部节点。四象限合起来就是答案。
最坏 O(n²)，可叶子总在半路把它刹住
复杂度看最坏：两棵树都细到 1×1 单格、一处都短路不了，节点数是 O(n²)，每个位置访问一次；只要撞上大块同色叶子，递归就在半路停下，实际常远快于此。递归只压着根到当前的一条路径，深度等于树高、约 log n 层，空间 O(log n)。边界上最小是 1×1；某块是全 1 叶子，那块铁定全 1、对方免看；某块是全 0 叶子，就把对方整块照搬。
几处最容易写反：全 1 叶子不短路还往下递归，纯是白费力气；全 0 叶子返回自己而非对方，那块就把对方图案抹没了；合并只盯着 val 相等、忘了要求四个都是叶子，一旦某个子结果其实是内部节点，就把一块花的区域错当纯色压平。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
三句口诀:叶子短路、四象限递归、同值合并。下面每一帧都在套它。
输入 · 矩阵 A：先看矩阵 A，对应第一棵四叉树。左上块四格全是 1，是一个全 1 叶子;右上块全是 0，是全 0 叶子;左下、右下两块颜色不纯，是内部节点。
输入 · 矩阵 B：再看矩阵 B，对应第二棵四叉树。它的右上块四格全是 1，是个全 1 叶子，其余三块都不纯。我们要算的，就是 A 按位或 B。
开始构建 · 结果矩阵：换成结果矩阵，现在四块都还是待定。两棵树的根都不是叶子，于是分别对左上、右上、左下、右下四个象限递归求或。
左上象限 · 看 A：先看左上象限。A 的左上块是一个 val 等于 1 的全 1 叶子。逻辑或里只要有一个 1，结果就是 1，所以这一整块或出来一定全是 1。
左上象限 · 短路定案：叶子短路第一种:当前是全 1 叶子，直接返回一个全 1 叶子，B 的左上块连看都不用看。左上象限四格全部填 1，定案。
右上象限 · 看 A：再看右上象限。A 的右上块是一个 val 等于 0 的全 0 叶子。0 或上任何东西，结果都等于那个东西。
右上象限 · 照搬 B：叶子短路第二种:当前是全 0 叶子，直接返回另一棵子树。B 的右上块是全 1 叶子，所以结果右上块照搬过来，也是全 1。
左下象限 · 两边都不纯：轮到左下象限。A、B 的左下块都不是叶子，谁也不能短路，那就只能把这一块拆成四个小格，分别求或。
左下小格 1 · 求或：左下第 1 格:A 这格是 1，B 这格是 0，按位或得 1。这格落定为 1。
左下小格 2 · 求或：左下第 2 格:A 这格是 0，B 这格是 1，按位或得 1。这格落定为 1。
左下小格 3 · 求或：左下第 3 格:A 这格是 0，B 这格是 1，按位或得 1。这格落定为 1。
左下小格 4 · 求或：左下第 4 格:A 这格是 1，B 这格是 0，按位或得 1。这格落定为 1。
左下象限 · 同值合并：四个小格或完都是 1，四个同值的叶子又凑成了一整块同色。按规则把它们合并成一个全 1 叶子，省掉一层结构。这就是同值合并。
右下象限 · 两边都不纯：最后是右下象限。A、B 的右下块也都不是叶子，照样拆成四个小格分别求或，看看这次能不能合并。
右下小格 1 · 求或：右下第 1 格:A 是 1，B 是 0，按位或得 1。这格是 1。
右下小格 2 · 求或：右下第 2 格:A 是 1，B 是 0，按位或得 1。这格是 1。
右下小格 3 · 求或：右下第 3 格:A 是 0，B 是 0，按位或得 0。注意这格两边都是 0，或还是 0。
右下小格 4 · 求或：右下第 4 格:A 是 0，B 是 1，按位或得 1。这格是 1。
右下象限 · 无法合并：右下四格是 1、1、0、1，不全相同。同值合并的条件不满足，不能并成一个叶子，只能保留成一个内部节点，下面挂着这四个叶子。
完成 · 结果矩阵：四个象限全部算完，结果矩阵就是 A 按位或 B。左上靠全 1 叶子短路，右上靠全 0 叶子照搬 B，左下四格同值合并成叶子，右下保留成内部节点。最深也只递归到 4×4 的单格，整棵树一次走完。
边界先想清:最小是 1×1;一边全 1 直接定全 1;一边全 0 直接照搬另一棵，无论对方多复杂。
面试重点:讲清分块短路省了多少访问，以及内部节点 val 为何无所谓。
参考代码
class Node: def __init__(self, val=False, isLeaf=False, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None): self.val = val self.isLeaf = isLeaf self.topLeft = topLeft self.topRight = topRight self.bottomLeft = bottomLeft self.bottomRight = bottomRightclass Solution: def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node': if quadTree1.isLeaf: return Node(True, True) if quadTree1.val else quadTree2 if quadTree2.isLeaf: return Node(True, True) if quadTree2.val else quadTree1 children = [ self.intersect(quadTree1.topLeft, quadTree2.topLeft), self.intersect(quadTree1.topRight, quadTree2.topRight), self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft), self.intersect(quadTree1.bottomRight, quadTree2.bottomRight), ] if all(c.isLeaf and c.val == children[0].val for c in children): return Node(children[0].val, True) return Node(True, False, *children)复杂度
- 时间：O(n²) 最坏，两棵树各有 O(n²) 个节点（n 为边长），每个位置最多访问一次;实际常因叶子短路提前结束，远小于此
- 空间：O(log n)，递归深度等于树高，约 log n 层（每层象限边长减半）;不计输出新建的结果树
易错点
面试追问把动画讲成自己的话
追问为什么在四叉树上直接做，比先还原成矩阵再逐格或更好？
追问题目说内部节点的 val 可以随便填，为什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
根据二叉树创建字符串
LeetCode 606 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题