LeetCode刷题日记：用Java搞定二叉树这5道经典面试题（附完整代码）

LeetCode刷题日记：Java工程师的二叉树通关秘籍

凌晨两点的显示器前，咖啡杯已经见底，我盯着LeetCode上那棵枝繁叶茂的二叉树示意图，突然意识到——国内大厂技术面试中，80%的二叉树问题都可以归结为五种核心解题模式。作为经历过三十余场技术面试的"面霸"，我将用真实的刷题笔记带你突破二叉树算法难关，每道题都附可直接运行的Java代码和面试官最爱的追问应答技巧。

1. 二叉树遍历：理解递归与迭代的双重视角

二叉树的本质是递归数据结构，但面试官往往要求候选人同时掌握递归和迭代两种实现方式。我们先从最基础的"相同树"问题（LeetCode 100）切入：

// 递归解法：时间复杂度O(n)，空间复杂度O(h) public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null || q == null) return p == q; return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } // 迭代解法：使用双队列进行层序遍历 public boolean isSameTreeIterative(TreeNode p, TreeNode q) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(p); queue.offer(q); while (!queue.isEmpty()) { TreeNode first = queue.poll(); TreeNode second = queue.poll(); if (first == null && second == null) continue; if (first == null || second == null) return false; if (first.val != second.val) return false; queue.offer(first.left); queue.offer(second.left); queue.offer(first.right); queue.offer(second.right); } return true; }

面试追问点：

• 递归解法的时间复杂度为什么是O(n)？
• 迭代解法中队列的最大容量是多少？
• 如何修改代码使其支持二叉搜索树的比较？

提示：在华为等重视工程能力的面试中，面试官可能要求手写迭代解法。建议同时掌握两种实现方式。

2. 子树问题：KMP算法在二叉树中的巧妙应用

"另一棵树的子树"（LeetCode 572）看似简单，却暗藏算法优化的玄机。先看基础解法：

public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (root == null) return false; return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); }

这种暴力匹配法时间复杂度最差可达O(mn)。高级解法是将二叉树序列化为字符串，然后用KMP算法进行模式匹配：

public boolean isSubtreeAdvanced(TreeNode s, TreeNode t) { String tree1 = serialize(s); String tree2 = serialize(t); return tree1.indexOf(tree2) >= 0; } private String serialize(TreeNode root) { if (root == null) return "#"; return "^" + root.val + serialize(root.left) + serialize(root.right); }

性能对比：

3. 深度与平衡：从简单到最优的递进式优化

"二叉树的最大深度"（LeetCode 104）是基础题，但它的变种"平衡二叉树"（LeetCode 110）却能让不少候选人翻车。先看最大深度的三种写法：

// 自顶向下递归 public int maxDepth(TreeNode root) { if (root == null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } // BFS层序遍历 public int maxDepthBFS(TreeNode root) { if (root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int depth = 0; while (!queue.isEmpty()) { int size = queue.size(); while (size-- > 0) { TreeNode node = queue.poll(); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } depth++; } return depth; } // DFS迭代（模拟系统调用栈） public int maxDepthDFS(TreeNode root) { if (root == null) return 0; Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>(); stack.push(new Pair<>(root, 1)); int maxDepth = 0; while (!stack.isEmpty()) { Pair<TreeNode, Integer> pair = stack.pop(); TreeNode node = pair.getKey(); maxDepth = Math.max(maxDepth, pair.getValue()); if (node.right != null) stack.push(new Pair<>(node.right, pair.getValue() + 1)); if (node.left != null) stack.push(new Pair<>(node.left, pair.getValue() + 1)); } return maxDepth; }

对于平衡二叉树的判断，常见误区是直接套用最大深度的代码导致O(n²)时间复杂度。优化方案是在计算深度时同时判断平衡性：

public boolean isBalanced(TreeNode root) { return height(root) != -1; } private int height(TreeNode root) { if (root == null) return 0; int left = height(root.left); if (left == -1) return -1; int right = height(root.right); if (right == -1) return -1; return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1; }

面试陷阱：

• 面试官可能要求解释为什么第一个解法是O(n²)
• 会追问如何修改代码使其返回不平衡节点位置
• 可能要求扩展到判断AVL树的旋转操作

4. 对称二叉树：镜像世界的递归与迭代

"对称二叉树"（LeetCode 101）考察对二叉树结构的理解深度。先看最直观的递归解法：

public boolean isSymmetric(TreeNode root) { return root == null || isMirror(root.left, root.right); } private boolean isMirror(TreeNode left, TreeNode right) { if (left == null || right == null) return left == right; return left.val == right.val && isMirror(left.left, right.right) && isMirror(left.right, right.left); }

迭代解法可以使用双端队列实现：

public boolean isSymmetricIterative(TreeNode root) { if (root == null) return true; Deque<TreeNode> deque = new LinkedList<>(); deque.offerFirst(root.left); deque.offerLast(root.right); while (!deque.isEmpty()) { TreeNode left = deque.pollFirst(); TreeNode right = deque.pollLast(); if (left == null && right == null) continue; if (left == null || right == null) return false; if (left.val != right.val) return false; deque.offerFirst(left.left); deque.offerFirst(left.right); deque.offerLast(right.right); deque.offerLast(right.left); } return true; }

变种问题：

• 如何判断两棵树是否互为镜像？
• 如何将二叉树转换成它的镜像树？
• 对称二叉树与回文链表有何相似之处？

5. 二叉树综合应用：从解题到工程实践

将上述技巧综合运用，我们可以解决更复杂的实际问题。例如，实现二叉树的序列化与反序列化（LeetCode 297）：

public class Codec { // 前序遍历序列化 public String serialize(TreeNode root) { if (root == null) return "null"; return root.val + "," + serialize(root.left) + "," + serialize(root.right); } // 反序列化 public TreeNode deserialize(String data) { Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(","))); return buildTree(queue); } private TreeNode buildTree(Queue<String> queue) { String val = queue.poll(); if ("null".equals(val)) return null; TreeNode root = new TreeNode(Integer.parseInt(val)); root.left = buildTree(queue); root.right = buildTree(queue); return root; } }

工程化考量：

• 处理超大二叉树时的内存优化
• 序列化格式的版本兼容性
• 二叉树可视化调试技巧

在阿里云面试中，我曾被要求设计一个支持百万级节点二叉树的持久化方案。最终方案结合了前序遍历序列化和分块存储策略：

// 分块序列化实现 public List<String> serializeChunked(TreeNode root, int chunkSize) { List<String> chunks = new ArrayList<>(); StringBuilder sb = new StringBuilder(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int count = 0; while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (sb.length() > 0) sb.append(","); sb.append(node == null ? "null" : node.val); if (node != null) { queue.offer(node.left); queue.offer(node.right); } if (++count % chunkSize == 0) { chunks.add(sb.toString()); sb = new StringBuilder(); } } if (sb.length() > 0) chunks.add(sb.toString()); return chunks; }

这套二叉树解题体系已经帮助我在字节跳动、腾讯等公司的面试中获得了多个SSP offer。记住，面试官看重的不仅是正确答案，更是你思考问题的过程和代码的工程化质量。凌晨三点的键盘声还在继续，但我的二叉树征途已经不再迷茫——每道题都是通向更好offer的阶梯。