题目描述
思路解析动画文字版
三句口诀:叶子短路、四象限递归、同值合并。下面每一帧都在套它。
输入 · 矩阵 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题