1. 二叉树高频题精讲从基础到进阶实战作为一名有多年开发经验的工程师我深知二叉树在算法面试和实际开发中的重要性。今天我将分享8道二叉树高频面试题的详细解析包含完整代码实现、解题思路和常见误区分析。这些题目覆盖了二叉树操作的核心考点掌握它们能帮助你在技术面试中游刃有余。2. 相同的树判断结构与值的双重验证2.1 问题分析与解题思路判断两棵树是否相同需要考虑两个维度结构相同和节点值相同。这是一个典型的递归问题我们需要从根节点开始逐层比较每个节点的结构和值。关键点在于先判断结构是否一致再比较节点值是否相等最后递归比较左右子树2.2 代码实现与复杂度分析public boolean isSameTree(TreeNode p, TreeNode q) { // 结构判断一个为空一个不为空 if (p ! null q null || p null q ! null) { return false; } // 两个都为空结构相同 if (p null q null) { return true; } // 值判断 if (p.val ! q.val) { return false; } // 递归比较左右子树 return isSameTree(p.left, q.left) isSameTree(p.right, q.right); }时间复杂度O(min(m,n))其中m和n分别是两棵树的节点数。空间复杂度O(min(h1,h2))h1和h2分别是两棵树的高度。2.3 常见错误与注意事项忘记先判断结构直接比较值可能导致空指针异常递归终止条件不完整导致无限递归没有考虑两棵树都为空的情况提示在实际面试中建议先画出简单的测试用例如空树、单节点树、不对称树等来验证算法正确性。3. 子树判断基于相同树判断的扩展3.1 问题理解与算法设计判断一棵树是否是另一棵树的子树需要满足子树结构必须完整包含不能多也不能少节点所有对应节点的值必须相同我们可以利用前面实现的isSameTree方法通过遍历主树的每个节点判断以该节点为根的子树是否与目标子树相同。3.2 代码实现与优化public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (root null) { return subRoot null; } // 当前节点开始的子树是否匹配 if (isSameTree(root, subRoot)) { return true; } // 递归检查左右子树 return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); }时间复杂度O(m×n)最坏情况下需要比较主树每个节点。空间复杂度O(max(h1,h2))。3.3 性能优化思路对于大规模树可以考虑以下优化先比较树高高度不同直接返回false使用哈希预处理子树特征如前序遍历序列使用KMP算法匹配树序列4. 翻转二叉树递归与迭代的经典应用4.1 问题解析与实现方案翻转二叉树即交换每个节点的左右子树。这是一个经典的递归问题也可以使用迭代法实现。4.2 递归实现public TreeNode invertTree(TreeNode root) { if (root null) { return null; } // 交换左右子树 TreeNode temp root.left; root.left root.right; root.right temp; // 递归翻转子树 invertTree(root.left); invertTree(root.right); return root; }4.3 迭代实现层序遍历public TreeNode invertTreeIterative(TreeNode root) { if (root null) return null; QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node queue.poll(); // 交换左右子节点 TreeNode temp node.left; node.left node.right; node.right temp; if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } return root; }4.4 应用场景与变种翻转二叉树在实际中有多种应用镜像树生成对称性检查某些特定遍历顺序需求5. 平衡二叉树判断高度差与递归结合5.1 平衡二叉树定义平衡二叉树是指任意节点的左右子树高度差不超过1。判断一棵树是否平衡需要计算每个节点的高度并比较。5.2 自顶向下解法public boolean isBalanced(TreeNode root) { if (root null) return true; int leftHeight height(root.left); int rightHeight height(root.right); return Math.abs(leftHeight - rightHeight) 1 isBalanced(root.left) isBalanced(root.right); } private int height(TreeNode node) { if (node null) return 0; return Math.max(height(node.left), height(node.right)) 1; }时间复杂度O(n²)因为每个节点的高度会被重复计算。5.3 自底向上优化public boolean isBalancedOptimized(TreeNode root) { return checkHeight(root) ! -1; } private int checkHeight(TreeNode node) { if (node null) return 0; int leftHeight checkHeight(node.left); if (leftHeight -1) return -1; int rightHeight checkHeight(node.right); if (rightHeight -1) return -1; if (Math.abs(leftHeight - rightHeight) 1) return -1; return Math.max(leftHeight, rightHeight) 1; }优化后时间复杂度O(n)每个节点只访问一次。6. 对称二叉树镜像对称判断6.1 问题分析与递归思路判断二叉树是否对称即判断其是否是自己的镜像。我们可以定义辅助函数判断两棵树是否是镜像。6.2 递归实现public boolean isSymmetric(TreeNode root) { if (root null) return true; return isMirror(root.left, root.right); } private boolean isMirror(TreeNode t1, TreeNode t2) { if (t1 null t2 null) return true; if (t1 null || t2 null) return false; return (t1.val t2.val) isMirror(t1.left, t2.right) isMirror(t1.right, t2.left); }6.3 迭代实现队列public boolean isSymmetricIterative(TreeNode root) { if (root null) return true; QueueTreeNode queue new LinkedList(); queue.offer(root.left); queue.offer(root.right); while (!queue.isEmpty()) { TreeNode t1 queue.poll(); TreeNode t2 queue.poll(); if (t1 null t2 null) continue; if (t1 null || t2 null) return false; if (t1.val ! t2.val) return false; queue.offer(t1.left); queue.offer(t2.right); queue.offer(t1.right); queue.offer(t2.left); } return true; }7. 二叉树遍历构建与遍历实战7.1 根据前序遍历字符串构建二叉树给定带有#表示空节点的前序遍历字符串构建二叉树并输出中序遍历结果。public class BinaryTreeBuilder { static class TreeNode { char val; TreeNode left, right; TreeNode(char val) { this.val val; } } private static int index 0; public static TreeNode buildTree(String str) { if (index str.length()) return null; char ch str.charAt(index); if (ch #) return null; TreeNode node new TreeNode(ch); node.left buildTree(str); node.right buildTree(str); return node; } public static void inOrder(TreeNode root) { if (root null) return; inOrder(root.left); System.out.print(root.val ); inOrder(root.right); } }7.2 注意事项index必须是全局或类变量不能在递归中重置处理完当前字符后要立即移动index输入可能有多组测试用例每次需要重置index8. 二叉树的层序遍历队列的应用8.1 基本层序遍历实现public ListListInteger levelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) return result; QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int levelSize queue.size(); ListInteger currentLevel new ArrayList(); for (int i 0; i levelSize; i) { TreeNode node queue.poll(); currentLevel.add(node.val); if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } result.add(currentLevel); } return result; }8.2 变种问题锯齿形层序遍历Zigzag层平均值计算每层最右/最左节点层序遍历的递归实现9. 二叉树最近公共祖先递归与路径追踪9.1 问题分析与递归解法最近公共祖先(LCA)是二叉树中的经典问题。递归解法思路如下如果当前节点是p或q返回当前节点在左右子树中递归查找p和q如果左右子树都找到节点当前节点就是LCA如果只有一边找到返回那边的结果public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root null || root p || root q) { return root; } TreeNode left lowestCommonAncestor(root.left, p, q); TreeNode right lowestCommonAncestor(root.right, p, q); if (left ! null right ! null) { return root; } return left ! null ? left : right; }9.2 迭代解法与路径追踪public TreeNode lowestCommonAncestorIterative(TreeNode root, TreeNode p, TreeNode q) { MapTreeNode, TreeNode parent new HashMap(); DequeTreeNode stack new ArrayDeque(); parent.put(root, null); stack.push(root); // 记录p和q的父节点路径 while (!parent.containsKey(p) || !parent.containsKey(q)) { TreeNode node stack.pop(); if (node.left ! null) { parent.put(node.left, node); stack.push(node.left); } if (node.right ! null) { parent.put(node.right, node); stack.push(node.right); } } // 找出p的所有祖先 SetTreeNode ancestors new HashSet(); while (p ! null) { ancestors.add(p); p parent.get(p); } // 找到q的祖先中第一个也是p的祖先的节点 while (!ancestors.contains(q)) { q parent.get(q); } return q; }9.3 性能比较与应用场景递归解法代码简洁但最坏情况下时间复杂度O(n)迭代解法需要额外空间存储父节点信息对于频繁查询的场景可以考虑预处理所有节点的父节点信息10. 二叉树问题实战技巧总结10.1 递归解题模板二叉树问题大多可以使用递归解决通用模板如下处理基准情况空节点或叶子节点处理当前节点逻辑递归处理左子树递归处理右子树合并左右子树结果10.2 迭代解题技巧当需要避免递归栈溢出或需要特定遍历顺序时可以使用迭代法使用栈模拟递归前序、中序、后序使用队列实现层序遍历使用双端队列实现锯齿形遍历10.3 常见错误与调试技巧忘记处理空指针情况递归终止条件不正确混淆值比较和引用比较修改树结构时丢失引用调试建议对于复杂递归问题可以先用小例子手动模拟递归过程验证思路正确性后再编码实现。10.4 性能优化方向避免重复计算如使用记忆化提前终止不必要的递归选择合适的数据结构栈、队列等利用二叉树特性进行剪枝在实际开发中二叉树操作是基础但重要的技能。掌握这些核心问题的解法不仅能帮助你在面试中表现出色也能在实际项目中高效处理树形数据结构。建议读者在理解这些解法后尝试在LeetCode上练习相关题目加深理解和记忆。