1. 二叉树算法实战从基础遍历到构造应用今天我想和大家分享几个二叉树相关的经典算法题目这些题目在面试和日常编码中经常出现。作为一名经历过多次算法面试的老手我深知掌握这些题目对提升编程能力的重要性。我们将从513题找树左下角的值开始逐步深入到更复杂的二叉树构造问题。2. 513. 找树左下角的值层序遍历的巧妙应用2.1 问题理解与解法思路这个问题要求我们找到二叉树最底层最左边的节点值。听起来简单但如何高效实现呢我最初尝试用递归深度优先搜索(DFS)但后来发现层序遍历(BFS)更适合这个问题。层序遍历就像逐层扫描二叉树从根节点开始先处理当前层所有节点再处理下一层。这种方法天然适合找最底层的需求因为我们能清晰地知道何时到达最后一层。2.2 代码实现与优化from collections import deque def findBottomLeftValue(root): if not root: return None queue deque([root]) result 0 while queue: level_size len(queue) for i in range(level_size): node queue.popleft() if i 0: # 记录每层第一个节点 result node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result这个实现有几个关键点使用双端队列(deque)实现高效的队列操作每次处理一层前记录该层第一个节点值最终保留的就是最后一层的第一个节点值提示在面试中解释清楚为什么选择BFS而不是DFS很重要。BFS能更直观地处理层的概念而DFS需要额外记录深度信息。3. 112 113. 路径总和问题递归与回溯的艺术3.1 路径总和I112题基础递归解法112题要求判断是否存在从根到叶子的路径其节点值之和等于给定目标。这是典型的递归问题def hasPathSum(root, targetSum): if not root: return False if not root.left and not root.right: # 叶子节点 return targetSum root.val return hasPathSum(root.left, targetSum - root.val) or \ hasPathSum(root.right, targetSum - root.val)3.2 路径总和II113题记录所有路径113题要求找出所有满足条件的路径这就需要回溯了def pathSum(root, targetSum): def backtrack(node, path, remaining): if not node: return path.append(node.val) if not node.left and not node.right and remaining node.val: result.append(list(path)) backtrack(node.left, path, remaining - node.val) backtrack(node.right, path, remaining - node.val) path.pop() # 关键回溯步骤 result [] backtrack(root, [], targetSum) return result这里的关键点是使用path列表记录当前路径到达叶子节点时检查是否满足条件在递归返回前弹出当前节点值回溯注意新手常犯的错误是忘记回溯步骤导致路径中包含不应该有的节点。我在第一次实现时就犯了这个错误调试了很久才发现。4. 二叉树构造从中序与后序遍历序列重建106题4.1 问题分析与递归思路这个问题要求根据中序和后序遍历序列重建二叉树。理解三种遍历方式的特性是关键后序遍历最后一个元素是根节点中序遍历根节点左边是左子树右边是右子树我的解决思路从后序序列获取根节点在中序序列中找到根节点位置递归构建左右子树4.2 代码实现与边界处理def buildTree(inorder, postorder): if not inorder or not postorder: return None root_val postorder[-1] root TreeNode(root_val) root_index inorder.index(root_val) root.left buildTree(inorder[:root_index], postorder[:root_index]) root.right buildTree(inorder[root_index1:], postorder[root_index:-1]) return root实际应用中需要注意序列为空的情况序列不匹配的情况题目假设输入有效切片操作的时间复杂度可以通过传递索引优化5. 从前序与中序遍历序列构造二叉树105题5.1 与前一道题的对比105题与106题类似只是把后序换成了前序。前序遍历的第一个元素是根节点def buildTree(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) root_index inorder.index(root_val) root.left buildTree(preorder[1:root_index1], inorder[:root_index]) root.right buildTree(preorder[root_index1:], inorder[root_index1:]) return root5.2 性能优化与常见错误这两道构造题都可以通过以下方式优化使用哈希表存储中序序列的值到索引的映射避免重复查找传递索引而非切片减少空间复杂度常见错误包括切片索引计算错误我经常在这里出错忽略空输入情况混淆前序和后序的根节点位置6. 二叉树算法实战经验分享经过这些题目的训练我总结出一些二叉树算法的通用技巧递归三要素终止条件通常是节点为空或到达叶子节点当前层处理逻辑递归调用左右子树遍历选择指南需要层信息 → BFS需要路径信息 → DFS构造问题 → 根据遍历特性选择切入点调试技巧小规模树手动模拟递归过程打印中间结果验证逻辑使用可视化工具观察树结构在实际面试中解释清楚思路比直接写代码更重要。我建议先说明算法选择理由再逐步实现最后讨论时间空间复杂度。例如对于路径总和问题时间复杂度是O(n)因为每个节点只访问一次空间复杂度在最坏情况下树退化为链表也是O(n)。 二叉树算法实战：遍历与构造技巧解析
1. 二叉树算法实战从基础遍历到构造应用今天我想和大家分享几个二叉树相关的经典算法题目这些题目在面试和日常编码中经常出现。作为一名经历过多次算法面试的老手我深知掌握这些题目对提升编程能力的重要性。我们将从513题找树左下角的值开始逐步深入到更复杂的二叉树构造问题。2. 513. 找树左下角的值层序遍历的巧妙应用2.1 问题理解与解法思路这个问题要求我们找到二叉树最底层最左边的节点值。听起来简单但如何高效实现呢我最初尝试用递归深度优先搜索(DFS)但后来发现层序遍历(BFS)更适合这个问题。层序遍历就像逐层扫描二叉树从根节点开始先处理当前层所有节点再处理下一层。这种方法天然适合找最底层的需求因为我们能清晰地知道何时到达最后一层。2.2 代码实现与优化from collections import deque def findBottomLeftValue(root): if not root: return None queue deque([root]) result 0 while queue: level_size len(queue) for i in range(level_size): node queue.popleft() if i 0: # 记录每层第一个节点 result node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result这个实现有几个关键点使用双端队列(deque)实现高效的队列操作每次处理一层前记录该层第一个节点值最终保留的就是最后一层的第一个节点值提示在面试中解释清楚为什么选择BFS而不是DFS很重要。BFS能更直观地处理层的概念而DFS需要额外记录深度信息。3. 112 113. 路径总和问题递归与回溯的艺术3.1 路径总和I112题基础递归解法112题要求判断是否存在从根到叶子的路径其节点值之和等于给定目标。这是典型的递归问题def hasPathSum(root, targetSum): if not root: return False if not root.left and not root.right: # 叶子节点 return targetSum root.val return hasPathSum(root.left, targetSum - root.val) or \ hasPathSum(root.right, targetSum - root.val)3.2 路径总和II113题记录所有路径113题要求找出所有满足条件的路径这就需要回溯了def pathSum(root, targetSum): def backtrack(node, path, remaining): if not node: return path.append(node.val) if not node.left and not node.right and remaining node.val: result.append(list(path)) backtrack(node.left, path, remaining - node.val) backtrack(node.right, path, remaining - node.val) path.pop() # 关键回溯步骤 result [] backtrack(root, [], targetSum) return result这里的关键点是使用path列表记录当前路径到达叶子节点时检查是否满足条件在递归返回前弹出当前节点值回溯注意新手常犯的错误是忘记回溯步骤导致路径中包含不应该有的节点。我在第一次实现时就犯了这个错误调试了很久才发现。4. 二叉树构造从中序与后序遍历序列重建106题4.1 问题分析与递归思路这个问题要求根据中序和后序遍历序列重建二叉树。理解三种遍历方式的特性是关键后序遍历最后一个元素是根节点中序遍历根节点左边是左子树右边是右子树我的解决思路从后序序列获取根节点在中序序列中找到根节点位置递归构建左右子树4.2 代码实现与边界处理def buildTree(inorder, postorder): if not inorder or not postorder: return None root_val postorder[-1] root TreeNode(root_val) root_index inorder.index(root_val) root.left buildTree(inorder[:root_index], postorder[:root_index]) root.right buildTree(inorder[root_index1:], postorder[root_index:-1]) return root实际应用中需要注意序列为空的情况序列不匹配的情况题目假设输入有效切片操作的时间复杂度可以通过传递索引优化5. 从前序与中序遍历序列构造二叉树105题5.1 与前一道题的对比105题与106题类似只是把后序换成了前序。前序遍历的第一个元素是根节点def buildTree(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) root_index inorder.index(root_val) root.left buildTree(preorder[1:root_index1], inorder[:root_index]) root.right buildTree(preorder[root_index1:], inorder[root_index1:]) return root5.2 性能优化与常见错误这两道构造题都可以通过以下方式优化使用哈希表存储中序序列的值到索引的映射避免重复查找传递索引而非切片减少空间复杂度常见错误包括切片索引计算错误我经常在这里出错忽略空输入情况混淆前序和后序的根节点位置6. 二叉树算法实战经验分享经过这些题目的训练我总结出一些二叉树算法的通用技巧递归三要素终止条件通常是节点为空或到达叶子节点当前层处理逻辑递归调用左右子树遍历选择指南需要层信息 → BFS需要路径信息 → DFS构造问题 → 根据遍历特性选择切入点调试技巧小规模树手动模拟递归过程打印中间结果验证逻辑使用可视化工具观察树结构在实际面试中解释清楚思路比直接写代码更重要。我建议先说明算法选择理由再逐步实现最后讨论时间空间复杂度。例如对于路径总和问题时间复杂度是O(n)因为每个节点只访问一次空间复杂度在最坏情况下树退化为链表也是O(n)。