二叉树算法实战：遍历与构造技巧解析-开发者社区

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 路径总和I（112题）：基础递归解法

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 路径总和II（113题）：记录所有路径

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_index+1:], 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_index+1], inorder[:root_index]) root.right = buildTree(preorder[root_index+1:], inorder[root_index+1:]) return root