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) { QueueTreeNode 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); }性能对比方法类型时间复杂度空间复杂度适用场景递归匹配O(mn)O(logm)小规模数据KMP优化O(mn)O(mn)大规模数据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; QueueTreeNode 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; DequePairTreeNode, Integer stack new ArrayDeque(); stack.push(new Pair(root, 1)); int maxDepth 0; while (!stack.isEmpty()) { PairTreeNode, 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; DequeTreeNode 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 297public 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) { QueueString queue new LinkedList(Arrays.asList(data.split(,))); return buildTree(queue); } private TreeNode buildTree(QueueString 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 ListString serializeChunked(TreeNode root, int chunkSize) { ListString chunks new ArrayList(); StringBuilder sb new StringBuilder(); QueueTreeNode 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的阶梯。