1. 二叉树面试通关指南概述作为一名经历过数十场技术面试的老兵我深知二叉树在面试中的霸主地位。无论是校招还是社招二叉树相关题目几乎占据了算法题的半壁江山。这份指南将系统梳理二叉树的核心知识点并搭配精选的力扣中低难度题目Java实现帮助你在面试中游刃有余。为什么选择中低难度题目根据我的面试官经验80%的考察都集中在基础知识的灵活运用上。那些炫技的高难度题在实际面试中出现的概率反而较低。本指南特别适合准备校招/社招的Java开发者需要快速复习二叉树核心概念的在职工程师希望建立系统性解题思路的算法初学者2. 二叉树核心知识点精讲2.1 二叉树基础概念二叉树Binary Tree是每个节点最多有两个子节点的树结构。先明确几个关键术语根节点(Root)没有父节点的节点叶子节点(Leaf)没有子节点的节点深度(Depth)从根到该节点的最长路径长度高度(Height)从该节点到叶子节点的最长路径特别要注意几种特殊二叉树满二叉树每个节点都有0或2个子节点完全二叉树除最后一层外完全填充且最后一层左对齐二叉搜索树(BST)左子树所有节点值 根节点值 右子树所有节点值// 基础二叉树节点定义 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } }2.2 二叉树遍历全解析遍历是二叉树最核心的操作面试中90%的题目都基于遍历的变种。必须掌握四种遍历方式及其实现前序遍历(Pre-order)根→左→右中序遍历(In-order)左→根→右BST中序遍历是有序序列后序遍历(Post-order)左→右→根层序遍历(Level-order)按层次从上到下从左到右递归实现简单直观但面试官更期待你能写出非递归实现。以下是前序遍历的两种实现// 递归版 void preOrderRecursive(TreeNode root) { if (root null) return; System.out.print(root.val ); preOrderRecursive(root.left); preOrderRecursive(root.right); } // 非递归版使用栈 void preOrderIterative(TreeNode root) { if (root null) return; StackTreeNode stack new Stack(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); System.out.print(node.val ); if (node.right ! null) stack.push(node.right); if (node.left ! null) stack.push(node.left); } }面试技巧当被要求实现遍历时先写出递归版然后说考虑到递归可能有栈溢出风险我还可以用栈/队列实现迭代版本。2.3 二叉树常见操作求深度/高度int maxDepth(TreeNode root) { if (root null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; }判断对称二叉树boolean isSymmetric(TreeNode root) { return root null || isMirror(root.left, root.right); } boolean isMirror(TreeNode left, TreeNode right) { if (left null right null) return true; if (left null || right null) return false; return left.val right.val isMirror(left.left, right.right) isMirror(left.right, right.left); }路径总和问题boolean hasPathSum(TreeNode root, int targetSum) { if (root null) return false; if (root.left null root.right null) return root.val targetSum; return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); }3. 力扣经典题目精解3.1 简单难度精选3.1.1 104. 二叉树的最大深度问题描述给定二叉树返回其最大深度。解题思路典型的递归问题。树的最大深度 1 左右子树最大深度中的较大值。public int maxDepth(TreeNode root) { if (root null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; }时间复杂度O(n)每个节点访问一次。3.1.2 101. 对称二叉树问题描述检查二叉树是否镜像对称。解题思路转化为判断左右子树是否镜像的问题。两个树镜像的条件根节点值相同每个树的右子树与另一个树的左子树镜像对称public boolean isSymmetric(TreeNode root) { return isMirror(root, root); } 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.right, t2.left) isMirror(t1.left, t2.right); }时间复杂度O(n)每个节点访问一次。3.2 中等难度精选3.2.1 102. 二叉树的层序遍历问题描述返回二叉树按层遍历的结果即逐层从左到右访问所有节点。解题思路使用队列进行BFS关键是要记录每层的节点数量。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; }时间复杂度O(n)每个节点进出队列一次。3.2.2 236. 二叉树的最近公共祖先问题描述给定二叉树和两个节点找到它们的最近公共祖先(LCA)。解题思路递归查找如果一个节点的左右子树分别包含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; }时间复杂度O(n)最坏情况下需要访问所有节点。4. 面试实战技巧与避坑指南4.1 二叉树问题解题框架根据我的面试经验二叉树问题大多可以套用以下框架确定遍历方式前序、中序、后序还是层序选择实现方法递归 or 迭代处理边界条件root为null的情况设计递归逻辑明确递归三要素终止条件当前层处理向下递归4.2 常见面试陷阱修改遍历顺序面试官可能要求之字形遍历或从下往上遍历解决方案层序遍历基础上隔层反转结果列表空间复杂度优化如Morris遍历实现O(1)空间的中序遍历核心思想利用叶子节点的空指针指向后继节点结合其他数据结构如将二叉树转为链表关键点在遍历过程中修改指针指向4.3 性能优化技巧剪枝优化在递归过程中提前终止不必要的分支// 在路径总和问题中的剪枝示例 if (hasPathSum(root.left, targetSum - root.val)) return true; // 如果左子树已经找到就不需要搜索右子树记忆化搜索对于重复计算的问题如二叉树直径存储中间结果迭代替代递归使用栈/队列实现遍历避免递归的栈溢出风险5. 高频面试题扩展训练5.1 二叉树直径问题问题描述二叉树的直径是任意两个节点间最长路径的长度。关键点直径可能不经过根节点需要计算每个节点的左右子树高度和。int maxDiameter 0; public int diameterOfBinaryTree(TreeNode root) { maxDepth(root); return maxDiameter; } private int maxDepth(TreeNode node) { if (node null) return 0; int left maxDepth(node.left); int right maxDepth(node.right); maxDiameter Math.max(maxDiameter, left right); return Math.max(left, right) 1; }5.2 从前序与中序遍历序列构造二叉树问题描述给定前序和中序遍历序列重建二叉树。解题思路前序第一个元素是根在中序中找到根的位置划分左右子树。public TreeNode buildTree(int[] preorder, int[] inorder) { return helper(0, 0, inorder.length - 1, preorder, inorder); } private TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) { if (preStart preorder.length - 1 || inStart inEnd) return null; TreeNode root new TreeNode(preorder[preStart]); int inIndex 0; // Index of current root in inorder for (int i inStart; i inEnd; i) { if (inorder[i] root.val) { inIndex i; break; } } root.left helper(preStart 1, inStart, inIndex - 1, preorder, inorder); root.right helper(preStart inIndex - inStart 1, inIndex 1, inEnd, preorder, inorder); return root; }5.3 二叉搜索树验证问题描述验证二叉树是否是有效的二叉搜索树。关键点中序遍历结果应该是有序的或者递归时传递值范围。public boolean isValidBST(TreeNode root) { return validate(root, null, null); } private boolean validate(TreeNode node, Integer low, Integer high) { if (node null) return true; if ((low ! null node.val low) || (high ! null node.val high)) return false; return validate(node.left, low, node.val) validate(node.right, node.val, high); }6. 面试前的终极检查清单在面试前请确保你已经掌握以下内容基础概念能清晰解释各种二叉树类型及其特性能手动绘制各种遍历顺序的示意图代码实现能熟练写出四种遍历的递归和迭代实现能处理常见的二叉树操作深度、对称性等解题思路看到题目能快速判断适用的遍历方式能分析时间/空间复杂度并提出优化方案边界条件空树处理单节点树处理只有左/右子树的情况沟通技巧能边写代码边解释思路能讨论不同解法的优劣能处理面试官的follow-up问题最后分享一个真实面试案例我曾被要求在白板上实现非递归的后序遍历关键是要理解前序→后序的转换关系前序是根→左→右后序是左→右→根可以调整为根→右→左然后反转结果。这种题目就非常考验对遍历本质的理解。 二叉树面试核心知识点与力扣题目精解
1. 二叉树面试通关指南概述作为一名经历过数十场技术面试的老兵我深知二叉树在面试中的霸主地位。无论是校招还是社招二叉树相关题目几乎占据了算法题的半壁江山。这份指南将系统梳理二叉树的核心知识点并搭配精选的力扣中低难度题目Java实现帮助你在面试中游刃有余。为什么选择中低难度题目根据我的面试官经验80%的考察都集中在基础知识的灵活运用上。那些炫技的高难度题在实际面试中出现的概率反而较低。本指南特别适合准备校招/社招的Java开发者需要快速复习二叉树核心概念的在职工程师希望建立系统性解题思路的算法初学者2. 二叉树核心知识点精讲2.1 二叉树基础概念二叉树Binary Tree是每个节点最多有两个子节点的树结构。先明确几个关键术语根节点(Root)没有父节点的节点叶子节点(Leaf)没有子节点的节点深度(Depth)从根到该节点的最长路径长度高度(Height)从该节点到叶子节点的最长路径特别要注意几种特殊二叉树满二叉树每个节点都有0或2个子节点完全二叉树除最后一层外完全填充且最后一层左对齐二叉搜索树(BST)左子树所有节点值 根节点值 右子树所有节点值// 基础二叉树节点定义 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } }2.2 二叉树遍历全解析遍历是二叉树最核心的操作面试中90%的题目都基于遍历的变种。必须掌握四种遍历方式及其实现前序遍历(Pre-order)根→左→右中序遍历(In-order)左→根→右BST中序遍历是有序序列后序遍历(Post-order)左→右→根层序遍历(Level-order)按层次从上到下从左到右递归实现简单直观但面试官更期待你能写出非递归实现。以下是前序遍历的两种实现// 递归版 void preOrderRecursive(TreeNode root) { if (root null) return; System.out.print(root.val ); preOrderRecursive(root.left); preOrderRecursive(root.right); } // 非递归版使用栈 void preOrderIterative(TreeNode root) { if (root null) return; StackTreeNode stack new Stack(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); System.out.print(node.val ); if (node.right ! null) stack.push(node.right); if (node.left ! null) stack.push(node.left); } }面试技巧当被要求实现遍历时先写出递归版然后说考虑到递归可能有栈溢出风险我还可以用栈/队列实现迭代版本。2.3 二叉树常见操作求深度/高度int maxDepth(TreeNode root) { if (root null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; }判断对称二叉树boolean isSymmetric(TreeNode root) { return root null || isMirror(root.left, root.right); } boolean isMirror(TreeNode left, TreeNode right) { if (left null right null) return true; if (left null || right null) return false; return left.val right.val isMirror(left.left, right.right) isMirror(left.right, right.left); }路径总和问题boolean hasPathSum(TreeNode root, int targetSum) { if (root null) return false; if (root.left null root.right null) return root.val targetSum; return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); }3. 力扣经典题目精解3.1 简单难度精选3.1.1 104. 二叉树的最大深度问题描述给定二叉树返回其最大深度。解题思路典型的递归问题。树的最大深度 1 左右子树最大深度中的较大值。public int maxDepth(TreeNode root) { if (root null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; }时间复杂度O(n)每个节点访问一次。3.1.2 101. 对称二叉树问题描述检查二叉树是否镜像对称。解题思路转化为判断左右子树是否镜像的问题。两个树镜像的条件根节点值相同每个树的右子树与另一个树的左子树镜像对称public boolean isSymmetric(TreeNode root) { return isMirror(root, root); } 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.right, t2.left) isMirror(t1.left, t2.right); }时间复杂度O(n)每个节点访问一次。3.2 中等难度精选3.2.1 102. 二叉树的层序遍历问题描述返回二叉树按层遍历的结果即逐层从左到右访问所有节点。解题思路使用队列进行BFS关键是要记录每层的节点数量。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; }时间复杂度O(n)每个节点进出队列一次。3.2.2 236. 二叉树的最近公共祖先问题描述给定二叉树和两个节点找到它们的最近公共祖先(LCA)。解题思路递归查找如果一个节点的左右子树分别包含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; }时间复杂度O(n)最坏情况下需要访问所有节点。4. 面试实战技巧与避坑指南4.1 二叉树问题解题框架根据我的面试经验二叉树问题大多可以套用以下框架确定遍历方式前序、中序、后序还是层序选择实现方法递归 or 迭代处理边界条件root为null的情况设计递归逻辑明确递归三要素终止条件当前层处理向下递归4.2 常见面试陷阱修改遍历顺序面试官可能要求之字形遍历或从下往上遍历解决方案层序遍历基础上隔层反转结果列表空间复杂度优化如Morris遍历实现O(1)空间的中序遍历核心思想利用叶子节点的空指针指向后继节点结合其他数据结构如将二叉树转为链表关键点在遍历过程中修改指针指向4.3 性能优化技巧剪枝优化在递归过程中提前终止不必要的分支// 在路径总和问题中的剪枝示例 if (hasPathSum(root.left, targetSum - root.val)) return true; // 如果左子树已经找到就不需要搜索右子树记忆化搜索对于重复计算的问题如二叉树直径存储中间结果迭代替代递归使用栈/队列实现遍历避免递归的栈溢出风险5. 高频面试题扩展训练5.1 二叉树直径问题问题描述二叉树的直径是任意两个节点间最长路径的长度。关键点直径可能不经过根节点需要计算每个节点的左右子树高度和。int maxDiameter 0; public int diameterOfBinaryTree(TreeNode root) { maxDepth(root); return maxDiameter; } private int maxDepth(TreeNode node) { if (node null) return 0; int left maxDepth(node.left); int right maxDepth(node.right); maxDiameter Math.max(maxDiameter, left right); return Math.max(left, right) 1; }5.2 从前序与中序遍历序列构造二叉树问题描述给定前序和中序遍历序列重建二叉树。解题思路前序第一个元素是根在中序中找到根的位置划分左右子树。public TreeNode buildTree(int[] preorder, int[] inorder) { return helper(0, 0, inorder.length - 1, preorder, inorder); } private TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) { if (preStart preorder.length - 1 || inStart inEnd) return null; TreeNode root new TreeNode(preorder[preStart]); int inIndex 0; // Index of current root in inorder for (int i inStart; i inEnd; i) { if (inorder[i] root.val) { inIndex i; break; } } root.left helper(preStart 1, inStart, inIndex - 1, preorder, inorder); root.right helper(preStart inIndex - inStart 1, inIndex 1, inEnd, preorder, inorder); return root; }5.3 二叉搜索树验证问题描述验证二叉树是否是有效的二叉搜索树。关键点中序遍历结果应该是有序的或者递归时传递值范围。public boolean isValidBST(TreeNode root) { return validate(root, null, null); } private boolean validate(TreeNode node, Integer low, Integer high) { if (node null) return true; if ((low ! null node.val low) || (high ! null node.val high)) return false; return validate(node.left, low, node.val) validate(node.right, node.val, high); }6. 面试前的终极检查清单在面试前请确保你已经掌握以下内容基础概念能清晰解释各种二叉树类型及其特性能手动绘制各种遍历顺序的示意图代码实现能熟练写出四种遍历的递归和迭代实现能处理常见的二叉树操作深度、对称性等解题思路看到题目能快速判断适用的遍历方式能分析时间/空间复杂度并提出优化方案边界条件空树处理单节点树处理只有左/右子树的情况沟通技巧能边写代码边解释思路能讨论不同解法的优劣能处理面试官的follow-up问题最后分享一个真实面试案例我曾被要求在白板上实现非递归的后序遍历关键是要理解前序→后序的转换关系前序是根→左→右后序是左→右→根可以调整为根→右→左然后反转结果。这种题目就非常考验对遍历本质的理解。