你写的二叉树递归全是错的——4道题踩坑实录（上）

文章目录

• 你写的二叉树递归全是错的——4道题踩坑实录（上）
• • 一、中序遍历：别让临时列表拖慢你
  • 二、对称二叉树：中序回文行不通
  • 三、二叉树直径：一个函数无法同时返回两个值
  • 四、层序遍历：锁定当前层大小是关键
  • 总结

你写的二叉树递归全是错的——4道题踩坑实录（上）

中序遍历、对称判断、直径计算、层序遍历，看起来都会写，但细节全是坑。

一、中序遍历：别让临时列表拖慢你

最常见的写法，每层递归都新建一个 tmp 列表再逐个复制：

// ❌ 慢写法
List<Integer> tmp = inorderTraversal(root.left);
for (Integer i : tmp) {
ans.add(i);
}

n 个节点，n 个临时对象，n 次拷贝。时间复杂度都是 O(n)，但常数项大很多。

正确做法：传同一个 List，直接 add

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
dfs(root, ans);
return ans;
}

private void dfs(TreeNode node, List<Integer> ans) {
if (node == null) return;
dfs(node.left, ans);
ans.add(node.val);
dfs(node.right, ans);
}
}

只创建一个 List，所有节点直接往里加，没有中间拷贝。

记住：能传引用就传引用，别在递归里反复 new 对象。

二、对称二叉树：中序回文行不通

直觉上觉得：对称树的中序遍历是回文 ——错的。

构造反例：

1
/ \\
3 2
/ / \\
2 3 1
/
1

中序遍历加哨兵后确实是回文，但这棵树明显不对称（左子树根=3，右子树根=2）。

根本原因：不同结构的树可以产生相同的中序序列。

还有第二个坑——用 != 比较 Integer 对象：

if (list.get(l) != list.get(r)) // ❌ 比较引用，不是值

Integer 缓存范围只有 -128~127，超出就翻车。

正确做法：直接递归判镜像

class Solution {
public boolean isSymmetric(TreeNode root) {
return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode l, TreeNode r) {
if (l == null && r == null) return true;
if (l == null || r == null || l.val != r.val) return false;
return isMirror(l.left, r.right)
&& isMirror(l.right, r.left);
}
}

核心只有一行：外侧对外侧，内侧对内侧。

三、二叉树直径：一个函数无法同时返回两个值

直径的定义：任意两节点之间路径的最大边数。

很多人的思路是把 diameterOfBinaryTree 直接递归，返回值当深度用：

// ❌ 错误
int left = diameterOfBinaryTree(root.left) + 1;
int right = diameterOfBinaryTree(root.right) + 1;
ans = Math.max(left + right, ans);
return Math.max(left, right);

问题：diameterOfBinaryTree 返回的是直径，不是深度。拿直径加 1 当深度，完全是两码事。

1
/ \\
2 3
/ \\
4 5

左子树深度 = 2，直径 = 2
代码算出 left = diameter(节点2) + 1 = 3 ❌

根本矛盾：一个函数只能有一个返回值，但这里需要向上传递"深度"，同时又要记录"直径"。

解法：用全局变量侧录直径，函数专心返回深度

class Solution {
int ans = 0;

public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return ans;
}

private int depth(TreeNode node) {
if (node == null) return 0;
int left = depth(node.left);
int right = depth(node.right);
ans = Math.max(ans, left + right); // 侧录直径
return Math.max(left, right) + 1; // 返回深度
}
}

直径 = 左深度 + 右深度；深度 = max(左深度, 右深度) + 1。两件事，必须分开。

四、层序遍历：锁定当前层大小是关键

层序遍历的难点在于：怎么区分哪些节点属于同一层？

常见错误思路：用额外的 tmp 列表存下一层，再倒回队列：

// ❌ 绕了一圈
List<TreeNode> tmp = new ArrayList<>();
while (!que.isEmpty()) {
TreeNode node = que.pollFirst();
if (node.left != null) tmp.add(node.left);
if (node.right != null) tmp.add(node.right);
}
for (TreeNode i : tmp) {
que.offerLast(i); // 又加回去
ansTmp.add(i.val);
}

多了一次循环，还有构造器传 int 的编译错误：

ans.add(new ArrayList<>(root.val)); // ❌ ArrayList 构造器接受 Collection，不接受 int

正确做法：进入每层前先记录队列大小

class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Deque<TreeNode> que = new ArrayDeque<>();
que.offerLast(root);
while (!que.isEmpty()) {
int size = que.size(); // 锁定当前层节点数
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = que.pollFirst();
level.add(node.val);
if (node.left != null) que.offerLast(node.left);
if (node.right != null) que.offerLast(node.right);
}
ans.add(level);
}
return ans;
}
}

int size = que.size() 是核心——入队子节点之前先锁定这一层的数量，for 循环精确处理完这一层再进下一层。

总结

一句话记住：

• 对象比较用 equals() 或直接比 .val（int）
• 递归函数返回值只能有一个语义
• BFS 分层靠的是进队前的 size 快照

觉得有帮助的话点个赞收藏，下篇继续二叉树进阶题。