京公网安备11010502063487号给定两棵二叉树，判断它们是否相同：结构相同，并且对应位置的结点值也相同。递归的想法很自然：两棵树都是空，相同；一棵空另一棵不空，不同；两个根的值不同，不同；否则左子树和右子树都必须相同。这道题是二叉树递归里最简单的一题，有一个常见的想法值得实测：能不能只比较两棵树的中序遍历序列？本文用穷举展示答案是不能，给出五种语言的实现，并把两棵树同时往下走的过程做成分步演示。
完整题目见官方页面（链接在文末）。树在测试里用 LeetCode 的层序数组表示。基准解是比较两棵树的层序数组（包含空位）是否完全相同，因为层序数组带着空位信息，它能完整地描述树的结构和值，是与递归比较不同的写法。一共 14 组用例，覆盖：官方三个示例、两棵都是空树、一棵空一棵非空、单个结点相同或不同、结构相同但某个值不同、结构不同（一个结点在左边还是右边）：
输入 [[1,2,3],[1,2,3]] 输出 true 输入 [[1,2],[1,null,2]] 输出 false 输入 [[1,2,1],[1,1,2]] 输出 false 输入 [[],[]] 输出 true 输入 [[],[1]] 输出 false 输入 [[1],[]] 输出 false
把两棵树都做中序遍历，得到两个数字序列，如果序列相同就认为树相同——这是错误的：不同形状的树可以有相同的中序序列。比如 [2, 1, 3]（2 是根，1、3 是左右孩子）和 [1, null, 2, null, 3]（1 → 2 → 3 的右链）的中序序列都是 1, 2, 3，但它们完全不同。下面是这种写法的真实结果，以及一个更强的穷举：用 1 到 n 组成的所有二叉搜索树，它们的中序序列全都是 1, 2, ..., n：
# 只比较中序遍历序列的写法（忽略了树的形状） [2, 1, 3] 与 [1, None, 2, None, 3]: 只比较中序 -> True solve -> False [1, None, 2, None, 3] 与 [3, 2, None, 1]: 只比较中序 -> True solve -> False [1, 2, 3] 与 [1, 2, 3]: 只比较中序 -> True solve -> True 穷举：用 1 到 n 组成的所有二叉搜索树（它们的中序序列全都是 1..n），任取两棵： n=3: 5 棵树，共 25 对（有序对），其中不同的有 20 对；只比较中序时全部 20 对不同的树都被误判为相同，solve 判对 20 对 n=4: 14 棵树，共 196 对（有序对），其中不同的有 182 对；只比较中序时全部 182 对不同的树都被误判为相同，solve 判对 182 对 n=5: 42 棵树，共 1764 对（有序对），其中不同的有 1722 对；只比较中序时全部 1722 对不同的树都被误判为相同，solve 判对 1722 对 n=6: 132 棵树，共 17424 对（有序对），其中不同的有 17292 对；只比较中序时全部 17292 对不同的树都被误判为相同，solve 判对 17292 对
n = 4 时有 14 棵不同的二叉搜索树（卡特兰数），它们共有 196 个有序对，其中 182 对是不同的树，只比较中序序列时这 182 对全部被误判成相同；n = 5、6 时同样是全部（1722 对、17292 对）被误判，而 solve 全部判对。要区分不同的树，中序序列必须再加上前序（或后序）序列，或者像本文这样直接递归比较结构。
isSameTree(p, q)：两个都是空返回真；只有一个是空返回假；两个根的值不同返回假；否则返回 isSameTree(p.left, q.left) 且 isSameTree(p.right, q.right)。所有的比较都是在两棵树的对应位置上同步进行的。时间 O(min(p 的结点数, q 的结点数))，空间是递归深度。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；测试程序把层序数组建成结点对象再调用。
Python · 解法代码class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def is_same_tree(p, q): if p is None and q is None: # 两边都空：相同 return True if p is None or q is None: # 一边空一边不空：结构不同 return False if p.val != q.val: # 结点的值不同 return False return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right) # 左右子树都要相同
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,2,3],[1,2,3]] → true [[1,2],[1,null,2]] → false [[1,2,1],[1,1,2]] → false [[],[]] → true [[],[1]] → false [[1],[]] → false
Java · 解法代码class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } } class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; // 两边都空：相同 if (p == null || q == null) return false; // 一边空一边不空：结构不同 if (p.val != q.val) return false; // 结点的值不同 return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 左右子树都要相同 } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,2,3],[1,2,3]] → true [[1,2],[1,null,2]] → false [[1,2,1],[1,1,2]] → false [[],[]] → true [[],[1]] → false [[1],[]] → false
Go · 解法代码type TreeNode struct { Val int Left, Right *TreeNode } func isSameTree(p *TreeNode, q *TreeNode) bool { if p == nil && q == nil { // 两边都空：相同 return true } if p == nil || q == nil { // 一边空一边不空：结构不同 return false } if p.Val != q.Val { // 结点的值不同 return false } return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right) // 左右子树都要相同 }
$ go build -o bin . && ./bin < cases.jsonl [[1,2,3],[1,2,3]] → true [[1,2],[1,null,2]] → false [[1,2,1],[1,1,2]] → false [[],[]] → true [[],[1]] → false [[1],[]] → false
JavaScript · 解法代码class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } } function isSameTree(p, q) { if (p === null && q === null) return true; // 两边都空：相同 if (p === null || q === null) return false; // 一边空一边不空：结构不同 if (p.val !== q.val) return false; // 结点的值不同 return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 左右子树都要相同 }
$ node run.js < cases.jsonl [[1,2,3],[1,2,3]] → true [[1,2],[1,null,2]] → false [[1,2,1],[1,1,2]] → false [[],[]] → true [[],[1]] → false [[1],[]] → false
C++ · 解法代码#include <vector> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if (!p && !q) return true; // 两边都空：相同 if (!p || !q) return false; // 一边空一边不空：结构不同 if (p->val != q->val) return false; // 结点的值不同 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); // 左右子树都要相同 } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,2,3],[1,2,3]] → true [[1,2],[1,null,2]] → false [[1,2,1],[1,1,2]] → false [[],[]] → true [[],[1]] → false [[1],[]] → false
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
Python 版本另外和"层序数组完全相同"做了随机对拍：结点数 0 到 8 的随机二叉树（值取 0 到 3），配对的另一棵树 40% 是完全相同的副本，30% 是改了一个结点的值，30% 是另一棵随机的树：
随机对拍 30000 组（结点数 0 到 8 的随机二叉树（值取 0 到 3）；配对的另一棵树 40% 是完全相同的副本，30% 是改了一个结点的值，30% 是另一棵随机的树），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。这道题只比较两棵树的重叠部分，是线性的，所以没有做规模对比实验。
下面的演示用两棵树：[1, 2, 3, 4] 和 [1, 2, 3, null, 5]。先比较根（1 和 1，相同），再比较左孩子（2 和 2，相同），然后比较 2 的左孩子：第一棵树里是 4，第二棵树里是空位，一棵空一棵不空，结构不同，返回 False。蓝色是正在比较的一对结点，绿色是已经确认相同的结点，琥珀色是发现不同的位置。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。