图 1：本文封面，「相等」的含义是结构与值逐对相同。
先说明属性：这是一篇经典题解析，题目出自本地历史面试资料，与任何公司的当前招聘无关。「判断两棵二叉树是否相等」是树题里的入门高频款，题面一句话——相等返回真，否则返回假，并说明算法复杂度。它考的不是思路多巧，而是你能不能把「相等」两个字拆成可执行的判定规则。
第一步，先定义「相等」。
两棵二叉树相等，当且仅当：根节点值相等，且左子树与左子树相等，且右子树与右子树相等。这个定义里藏着本题最关键的一点——「相等」是「结构 + 值」的双重比较。两棵树节点值集合完全相同，只要形状不同（比如一个节点在左孩子位置、另一个在右孩子位置），也不算相等。空节点不是「没有信息」，空本身就是结构信息，必须参与比较。
第二步，递归写法：四条出口。
递归天然匹配这个自相似定义。对当前这一对节点，只有四种情况：两个都为空，这一对相等，返回真；一个空一个不空，结构已经不同，返回假；都不空但值不等，返回假；值相等，那就继续递归比较左子树对和右子树对，两边都真才算真。代码几乎就是把定义誊写一遍。
第三步，迭代写法：队列成对入队。
如果面试官追问「递归深度太大怎么办」，就轮到迭代出场。思路是把递归的隐式调用栈换成显式队列：队列里每次放一对「待比较的节点对」，初始放两个根；每轮取出一对做同样的四出口判断，都不空且值相等时，把两棵子树的对应孩子成对压入队列——左对左、右对右。空节点用 null 占位照常入队，轮到它时靠「两个都空就跳过」的出口消化。队列清空说明所有对应位置都比过，两树相等。这本质上就是两棵树同步做层序遍历。
第四步，写出可运行代码并实测边界。
下面这份实现包含递归与迭代两种写法，用 Node.js 22.15.0 直接运行（node same-tree.js）即可，内置五组用例：完全相同、双空树、值同结构不同、结构同值不同、一空一不空：
'use strict';
// 建树：用数组按层序构造二叉树，null 表示空节点
function buildTree(arr) {
if (arr.length === 0 || arr[0] === null) return null;
const nodes = arr.map((v) => (v === null ? null : { val: v, left: null, right: null }));
for (let i = 0; i < nodes.length; i++) {
if (!nodes[i]) continue;
const li = 2 * i + 1;
const ri = 2 * i + 2;
if (li < nodes.length) nodes[i].left = nodes[li];
if (ri < nodes.length) nodes[i].right = nodes[ri];
}
return nodes[0];
}
// 写法一：递归。四条出口一目了然
function isSameTreeRecursive(p, q) {
if (p === null && q === null) return true; // 都为空：结构相同
if (p === null || q === null) return false; // 一空一不空：结构不同
if (p.val !== q.val) return false; // 值不等
return isSameTreeRecursive(p.left, q.left) && isSameTreeRecursive(p.right, q.right);
}
// 写法二：层序迭代。队列里成对入队，空节点用 null 占位参与比较
function isSameTreeIterative(p, q) {
const queue = [[p, q]];
while (queue.length > 0) {
const [a, b] = queue.shift();
if (a === null && b === null) continue; // 这一对都空，跳过
if (a === null || b === null) return false;
if (a.val !== b.val) return false;
queue.push([a.left, b.left], [a.right, b.right]);
}
return true;
}
const cases = [
{ name: '完全相同', p: [1, 2, 3], q: [1, 2, 3], expect: true },
{ name: '都为空树', p: [], q: [], expect: true },
{ name: '值相同结构不同（左右互换）', p: [1, 2], q: [1, null, 2], expect: false },
{ name: '结构相同值不同', p: [1, 2, 1], q: [1, 1, 2], expect: false },
{ name: '一棵为空', p: [1], q: [], expect: false },
];
for (const c of cases) {
const p = buildTree(c.p);
const q = buildTree(c.q);
const r1 = isSameTreeRecursive(p, q);
const r2 = isSameTreeIterative(p, q);
console.log(`${c.name}：递归=${r1}，迭代=${r2}，预期=${c.expect} ${r1 === c.expect && r2 === c.expect ? '通过' : '失败'}`);
}
实测输出：
完全相同：递归=true，迭代=true，预期=true 通过
都为空树：递归=true，迭代=true，预期=true 通过
值相同结构不同（左右互换）：递归=false，迭代=false，预期=false 通过
结构相同值不同：递归=false，迭代=false，预期=false 通过
一棵为空：递归=false，迭代=false，预期=false 通过
注意第三组用例：[1, 2] 和 [1, null, 2] 节点值集合一模一样，只是一个把 2 挂在左孩子、一个挂在右孩子，结果必须是不等——这就是「结构参与比较」的试金石，很多错误答案恰恰在这一组上露馅。
图 2：递归与迭代两种写法对照，四出口判定是共同核心。
可能的追问与易错点。
「时间空间复杂度？」两个写法的时间复杂度都是 O(n)，n 取两棵树节点的较小值——每个节点对最多比一次；空间上递归是 O(h) 调用栈，h 为树高，迭代是 O(w) 队列，w 为最大层宽。易错点集中在三处：只比值不比结构，左右互换的树被误判为相等；迭代时忘记把空节点也成对入队，导致结构差异漏检；对极深的树用递归，撞上调用栈上限才想起该换迭代。
这套「结构 + 值」双重比较的建模方式不止属于面试：比较两棵抽象语法树是否等价、给两棵配置树做 diff、测试断言里判断两个 JSON 结构是否一致，都是同一个动作的变体——先定义「相等的递归结构」，再选递归或迭代去执行。回到面试现场，建议的答题节奏：先给定义与递归四出口，主动交代复杂度，再补一句「树太深可换层序迭代」，最后落笔写码。你刷树题时在「空节点也是信息」上栽过跟头吗？欢迎分享。