LeetCode 558中等树 · BST
四叉树交集 图解题解
这道题到底在问什么
四叉树的每个节点要么是叶子（isLeaf=True，整块同值，val 是 0 或 1），要么有四个孩子，分别对应左上、右上、左下、右下四个象限。两个矩阵按位或，就是对应位置只要有一个 1，结果就是 1。我们要在四叉树上直接算出这个或。
- 输入
- A、B 各是一个 4×4 的 0/1 矩阵
- 输出
- 它们按位或后的矩阵，用四叉树表示
最优解：一步一步想明白
- 3三句口诀:叶子短路、四象限递归、同值合并。下面每一帧都在套它。
- 4四叉树1先看矩阵 A，对应第一棵四叉树。左上块四格全是 1，是一个全 1 叶子;右上块全是 0，是全 0 叶子;左下、右下两块颜色不纯，是内部节点。
- 5四叉树2再看矩阵 B，对应第二棵四叉树。它的右上块四格全是 1，是个全 1 叶子，其余三块都不纯。我们要算的，就是 A 按位或 B。
- 6逐象限求或换成结果矩阵，现在四块都还是待定。两棵树的根都不是叶子，于是分别对左上、右上、左下、右下四个象限递归求或。
- 7A 左上 = 全 1 叶子先看左上象限。A 的左上块是一个 val 等于 1 的全 1 叶子。逻辑或里只要有一个 1，结果就是 1，所以这一整块或出来一定全是 1。
- 8左上 = 全 1叶子短路第一种:当前是全 1 叶子，直接返回一个全 1 叶子，B 的左上块连看都不用看。左上象限四格全部填 1，定案。
- 9A 右上 = 全 0 叶子再看右上象限。A 的右上块是一个 val 等于 0 的全 0 叶子。0 或上任何东西，结果都等于那个东西。
- 10右上 = B 的右上叶子短路第二种:当前是全 0 叶子，直接返回另一棵子树。B 的右上块是全 1 叶子，所以结果右上块照搬过来，也是全 1。
- 11需要拆 4 小格轮到左下象限。A、B 的左下块都不是叶子，谁也不能短路，那就只能把这一块拆成四个小格，分别求或。
- 12A 1 或 B 0 = 1左下第 1 格:A 这格是 1，B 这格是 0，按位或得 1。这格落定为 1。
- 13A 0 或 B 1 = 1左下第 2 格:A 这格是 0，B 这格是 1，按位或得 1。这格落定为 1。
- 14A 0 或 B 1 = 1左下第 3 格:A 这格是 0，B 这格是 1，按位或得 1。这格落定为 1。
- 15A 1 或 B 0 = 1左下第 4 格:A 这格是 1，B 这格是 0，按位或得 1。这格落定为 1。
- 16四个 1 → 合并成一个叶子四个小格或完都是 1，四个同值的叶子又凑成了一整块同色。按规则把它们合并成一个全 1 叶子，省掉一层结构。这就是同值合并。
- 17同样拆 4 小格最后是右下象限。A、B 的右下块也都不是叶子，照样拆成四个小格分别求或，看看这次能不能合并。
- 18A 1 或 B 0 = 1右下第 1 格:A 是 1，B 是 0，按位或得 1。这格是 1。
- 19A 1 或 B 0 = 1右下第 2 格:A 是 1，B 是 0，按位或得 1。这格是 1。
- 20A 0 或 B 0 = 0右下第 3 格:A 是 0，B 是 0，按位或得 0。注意这格两边都是 0，或还是 0。
- 21A 0 或 B 1 = 1右下第 4 格:A 是 0，B 是 1，按位或得 1。这格是 1。
- 221 1 0 1 不全相同右下四格是 1、1、0、1，不全相同。同值合并的条件不满足，不能并成一个叶子，只能保留成一个内部节点，下面挂着这四个叶子。
- 23A 或 B 完成四个象限全部算完，结果矩阵就是 A 按位或 B。左上靠全 1 叶子短路，右上靠全 0 叶子照搬 B，左下四格同值合并成叶子，右下保留成内部节点。最深也只递归到 4×4 的单格，整棵树一次走完。
⚠️ 容易写错的地方
✗ 错：叶子 val=1 时还去递归孩子
✓ 对：全 1 叶子直接返回全 1，不再下探
全 1 或任何东西都是全 1，递归是白费力气
✗ 错：叶子 val=0 时返回自己
✓ 对：应返回另一棵子树
0 或 x 等于 x，结果取决于对方那块
✗ 错：四子结果只看 val 相同就合并
✓ 对：必须四个都是叶子且 val 相同
只要有一个是内部节点，这块就不是纯色，不能并成叶子
完整代码（Python / C++ / Java）
Python
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 = bottomRight
class 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)C++
#include <iostream>
#include <vector>
using namespace std;
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft;
Node* topRight;
Node* bottomLeft;
Node* bottomRight;
Node() : val(false), isLeaf(false), topLeft(nullptr), topRight(nullptr), bottomLeft(nullptr), bottomRight(nullptr) {}
Node(bool _val, bool _isLeaf) : val(_val), isLeaf(_isLeaf), topLeft(nullptr), topRight(nullptr), bottomLeft(nullptr), bottomRight(nullptr) {}
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* intersect(Node* a, Node* b) {
if (a->isLeaf) return a->val ? new Node(true, true) : b;
if (b->isLeaf) return b->val ? new Node(true, true) : a;
Node* tl = intersect(a->topLeft, b->topLeft);
Node* tr = intersect(a->topRight, b->topRight);
Node* bl = intersect(a->bottomLeft, b->bottomLeft);
Node* br = intersect(a->bottomRight, b->bottomRight);
if (tl->isLeaf && tr->isLeaf && bl->isLeaf && br->isLeaf && tl->val == tr->val && tl->val == bl->val && tl->val == br->val) return new Node(tl->val, true);
return new Node(true, false, tl, tr, bl, br);
}
};Java
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
public Node() {}
public Node(boolean val, boolean isLeaf) { this.val = val; this.isLeaf = isLeaf; }
public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
this.val = val; this.isLeaf = isLeaf; this.topLeft = topLeft; this.topRight = topRight; this.bottomLeft = bottomLeft; this.bottomRight = bottomRight;
}
}
class Solution {
public Node intersect(Node a, Node b) {
if (a.isLeaf) return a.val ? new Node(true, true) : b;
if (b.isLeaf) return b.val ? new Node(true, true) : a;
Node tl = intersect(a.topLeft, b.topLeft), tr = intersect(a.topRight, b.topRight), bl = intersect(a.bottomLeft, b.bottomLeft), br = intersect(a.bottomRight, b.bottomRight);
if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf && tl.val == tr.val && tl.val == bl.val && tl.val == br.val) return new Node(tl.val, true);
return new Node(true, false, tl, tr, bl, br);
}
}复杂度
时间
O(n²) 最坏
两棵树各有 O(n²) 个节点（n 为边长），每个位置最多访问一次;实际常因叶子短路提前结束，远小于此
空间
O(log n)
递归深度等于树高，约 log n 层（每层象限边长减半）;不计输出新建的结果树
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 四叉树交集 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么在四叉树上直接做，比先还原成矩阵再逐格或更好？+
因为大块同色时能一步处理。一个全 1 或全 0 的叶子可能覆盖巨大的区域，短路一次就跳过整块，省去对里面每一格的访问。还原成矩阵会强行展开到 n×n，丢掉了这种分块优势。
题目说内部节点的 val 可以随便填，为什么？+
因为对内部节点而言 val 没有语义，只有叶子的 val 表示那块区域的颜色。判题只看叶子的取值和树的结构，所以内部节点的 val 填 0 或 1 都会被接受，通常约定填 true。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 四叉树交集 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。