二叉树面试题通关模板

二叉树面试题通关模板这套模板背下来，面试不丢分ALGORITHMINTERVIEWGUIDE·2024内容导航01二叉树核心概念回顾02遍历算法：递归与迭代模板03经典题型实战解析04解题心法与避坑指南05总结与面试技巧二叉树核心概念回顾▍核心定义每个节点最多有两个子节点的树结构，严格区分为左子树和右子树，是树形结构中最基础且应用最广泛的类型。▍常见分类满二叉树：除叶子节点外，每个节点都有两个子节点。完全二叉树：按层序遍历，节点位置与同深度满二叉树完全对应。平衡二叉树：左右子树的高度差绝对值不超过1，确保查询效率。二叉搜索树(BST)：左子树值<根节点值<右子树值。图示：四种二叉树结构形态对比遍历算法总览遍历是二叉树一切操作的基础，主要有四种核心方式：前序遍历(Pre-order)：根→左→右中序遍历(In-order)：左→根→右后序遍历(Post-order)：左→右→根层序遍历(Level-order)：逐层访问图示：二叉树四种遍历方式的路径与顺序对比前序遍历-递归模板▍核心逻辑遵循“根-左-右”的访问顺序：先访问当前根节点，再递归遍历左子树，最后递归遍历右子树。▍代码模板(Python)defpreorderTraversal(root):ifnotroot:return[]res=[root.val]#根res+=preorderTraversal(root.left)#左res+=preorderTraversal(root.right)#右returnres▍关键点递归的终止条件是节点为空（None），这是防止栈溢出的基础。递归执行流程可视化前序遍历-迭代模板▍核心逻辑利用栈模拟递归过程，先将根节点入栈，然后循环出栈，访问节点，并将右子节点和左子节点依次入栈。▍代码模板(Python)defpreorderTraversal(root):ifnotroot:return[]stack,res=[root],[]whilestack:node=stack.pop()res.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnres▍关键点栈是后进先出结构，因此必须先入栈右子节点，再入栈左子节点，以保证出栈顺序为“根-左-右”。迭代过程示意图中序遍历-递归模板▍核心逻辑(Left-Root-Right)遵循“左子树→根节点→右子树”的访问顺序，是二叉树遍历的基础算法之一。definorderTraversal(root):ifnotroot:return[]res=[]res+=inorderTraversal(root.left)#左res.append(root.val)#根res+=inorderTraversal(root.right)#右returnres▍关键特性对于二叉搜索树(BST)，中序遍历的输出结果严格保持升序排列。这一特性常用于验证BST合法性或寻找第k小元素。中序遍历递归执行流程示意中序遍历-迭代模板核心逻辑利用栈和指针，先将所有左子节点入栈，出栈访问节点后处理右子节点。Python代码模板definorderTraversal(root):stack,res,curr=[],[],rootwhilecurrorstack:whilecurr:#遍历左子树stack.append(curr);curr=curr.leftcurr=stack.pop()#访问节点res.append(curr.val);curr=curr.rightreturnres关键点必须使用指针(curr)来控制左子树的遍历过程。图示：中序遍历迭代过程(左-根-右)记忆口诀：指针一路向左冲，无路可走再出栈，转向右边继续冲。后序遍历-递归模板核心逻辑(Left-Right-Root)遵循“左子树→右子树→根节点”的访问顺序。先递归处理完所有子节点，最后才处理当前节点。Python代码模板defpostorderTraversal(root):ifnotroot:return[]res=[]res+=postorderTraversal(root.left)res+=postorderTraversal(root.right)res.append(root.val)returnres应用场景常用于需要先处理子节点再处理父节点的场景，例如树的销毁操作（先释放子节点内存）。图示：递归遍历过程（左→右→根）后序遍历-迭代模板▍核心逻辑利用两个栈协同工作：栈1负责节点遍历，栈2负责暂存结果。通过特定的入栈顺序（根→右→左），最终栈2的出栈顺序即为后序遍历（左→右→根）。▍代码模板(Python)defpostorderTraversal(root):ifnotroot:return[]stack1,stack2,res=[root],[],[]whilestack1:node=stack1.pop()#根节点出栈stack2.append(node)#压入结果栈ifnode.left:stack1.append(node.left)ifnode.right:stack1.append(node.right)whilestack2:res.append(stack2.pop().val)returnres▍关键点先将左子节点入栈，再将右子节点入栈，利用栈“先进后出”的特性，保证出栈顺序为“右→左”，最终实现后序。图：后序遍历迭代过程栈状态变化层序遍历-迭代模板核心逻辑(BFS)利用队列先进先出特性，根节点入队后循环出队，访问节点并将其左右子节点依次入队。Python代码实现deflevelOrder(root):ifnotroot:return[]queue,res=[root],[]whilequeue:level=[]for_inrange(len(queue)):node=queue.pop(0)level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)returnres关键点：通过len(queue)锁定当前层节点数，确保按层处理。图示：树的层序遍历与队列操作流程经典题型一：二叉树的最大深度▍题目描述给定一个二叉树，找出其最大深度。深度是从根节点到最远叶子节点的最长路径上的节点数。▍解题思路采用递归法：树的最大深度等于其左子树的最大深度与右子树的最大深度中的较大值，再加1（根节点本身）。Python代码模板：defmaxDepth(root):ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))▍复杂度分析•时间复杂度：O(n)，每个节点仅访问一次。•空间复杂度：O(h)，h为树的高度，取决于递归栈深度。图示：二叉树最大深度计算逻辑数据结构与算法系列课程/经典递归应用经典题型二：路径总和题目描述：给定二叉树和目标和，判断是否存在根到叶子的路径，路径节点值之和等于目标和。解题思路：递归法。从根开始，每次用目标和减当前节点值，到达叶子时判断剩余值是否等于叶子值。defhasPathSum(root,targetSum):ifnotroot:returnFalseifnotroot.leftandnotroot.right:returnroot.val==targetSumreturnhasPathSum(root.left,targetSum-root.val)orhasPathSum(root.right,targetSum-root.val)复杂度分析：时间复杂度O(n)，空间复杂度O(h)(h为树的高度)。路径权重计算示意图AlgorithmInterviewPreparation/BinaryTreeSeries经典题型三：最近公共祖先题目描述给定一个二叉树，找到该树中两个指定节点的最近公共祖先。解题思路(递归法)若当前节点是p/q则返回；若左右子树均找到目标，则当前节点是LCA；若仅单边找到，则返回该边结果。Python代码模板deflowestCommonAncestor(root,p,q):ifnotrootorroot==porroot==q:returnrootleft,right=self.lowestCommonAncestor(root.left,p,q),self.lowestCommonAncestor(root.right,p,q)returnrootifleftandrightelseleftifleftelseright时间复杂度O(n)，空间复杂度O(h)(h为树高)图示：最近公共祖先查找逻辑经典题型四：验证二叉搜索树题目描述给定一个二叉树，判断其是否是一个有效的二叉搜索树（BST）。解题思路：中序遍历法利用二叉搜索树“中序遍历结果为升序”的特性，通过迭代遍历，检查当前节点值是否严格大于前一个节点值。Python代码模板defisValidBST(root):stack,prev=[],float('-inf')whilestackorroot:whileroot:stack.append(root);root=root.leftroot=stack.pop();ifroot.val<=prev:returnFalseprev,root=root.val,root.rightreturnTrue二叉搜索树结构示意图复杂度分析：时间复杂度O(n)（遍历所有节点），空间复杂度O(h)（h为树的高度，取决于递归栈深度）。解题心法：遍历思维vs分解问题思维遍历思维(Traversal)通过遍历整棵树获取信息，配合外部变量记录结果。适用于路径收集、特征统计等场景。分解问题思维(Decomposition)将原问题拆解为子树问题，通过子问题的解推导原问题的解。适用于求深度、判断平衡等场景。解题核心步骤1.聚焦单个节点思考职责；2.确定执行时机（前/中/后序位置）。图示：二叉树节点关系与查找逻辑避坑指南：常见错误与优化技巧常见错误(CommonPitfalls)递归终止条件不明确，导致栈溢出或逻辑错误。迭代遍历顺序错误，栈或队列操作顺序混乱。忽略边界值，处理二叉搜索树时未考虑极值。优化技巧(OptimizationTips)利用哈希表存储节点信息，将时间复杂度降至O(1)。路径问题回溯法，避免重复计算，节省空间。利用特殊结构性质（如完全二叉树）进行针对性优化。总结：二叉树面试通关要点基础打牢熟练掌握四种遍历的递归和迭代实现，这是解决所有树相关问题的基石。模板背熟牢记最大深度、路径和、最近公共祖先等核心题型的解题模板，快速上手。思维灵活深刻理解遍历思维（前中后序）和分解问题思维，根据题目特性灵活切换。细节注意编写代码时注意空指针等边界条件，面试中主动分析时间与空间复杂度。C