用Python搞定二叉树侧视图：从PTA天梯赛真题到面试常考题的保姆级解法

用Python搞定二叉树侧视图从PTA天梯赛真题到面试常考题的保姆级解法在技术面试中二叉树问题几乎是必考内容而侧视图问题因其能同时考察递归、树遍历和层序处理等多个核心概念成为大厂面试官的最爱之一。这道源自PTA天梯赛的真题完美融合了中序/后序建树和层序遍历两大难点是检验候选人算法功底的绝佳试金石。本文将带你用Python从零实现这一经典问题掌握可复用的解题模板轻松应对LeetCode 199等同类题型。1. 理解问题本质为什么侧视图是面试高频考点二叉树侧视图问题之所以备受青睐在于它巧妙地将多个基础知识点串联起来建树能力需要根据中序和后序遍历序列重建二叉树遍历技巧必须掌握层序遍历BFS的实现数据处理要能从层序结果中提取首尾元素空间优化需要考虑如何高效存储中间结果实际面试中面试官可能会先问如何根据两种遍历序列重建树再延伸问如何获取树的左右视图最后可能要求优化空间复杂度。这道题的价值在于它能一次性考察候选人对树结构的理解深度。提示在亚马逊和微软的面试反馈中约65%的候选人在二叉树侧视图问题上会暴露出递归理解不深或层序遍历实现不熟练的问题。2. 从零构建二叉树中序后序的Python解法重建二叉树是解决侧视图问题的第一步。给定中序和后序遍历序列我们需要明确几个关键点后序序列的最后一个元素是当前子树的根节点在中序序列中找到根节点位置左侧为左子树右侧为右子树递归处理左右子树class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def buildTree(inorder, postorder): if not inorder or not postorder: return None root_val postorder[-1] root TreeNode(root_val) root_pos inorder.index(root_val) root.left buildTree(inorder[:root_pos], postorder[:root_pos]) root.right buildTree(inorder[root_pos1:], postorder[root_pos:-1]) return root这个递归解法的时间复杂度是O(n^2)因为每次都要在中序序列中查找根节点位置。对于面试场景可以先用哈希表预处理中序序列的位置信息def buildTreeOpt(inorder, postorder): inorder_map {val:idx for idx, val in enumerate(inorder)} def helper(in_start, in_end, post_start, post_end): if in_start in_end: return None root_val postorder[post_end] root TreeNode(root_val) root_pos inorder_map[root_val] left_size root_pos - in_start root.left helper(in_start, root_pos-1, post_start, post_startleft_size-1) root.right helper(root_pos1, in_end, post_startleft_size, post_end-1) return root return helper(0, len(inorder)-1, 0, len(postorder)-1)优化后的版本将时间复杂度降到了O(n)空间复杂度为O(n)哈希表存储开销这是面试中最希望看到的实现方式。3. 获取侧视图层序遍历的巧妙应用得到二叉树后我们需要通过层序遍历获取左右视图。层序遍历的标准BFS实现大家应该很熟悉from collections import deque def levelOrder(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result获取侧视图的关键在于右视图每层的最后一个元素左视图每层的第一个元素我们可以直接利用层序遍历的结果来提取这些元素def getSideViews(root): levels levelOrder(root) left_view [level[0] for level in levels] right_view [level[-1] for level in levels] return left_view, right_view这种实现清晰易懂但面试官可能会追问空间优化的问题。实际上我们可以在BFS过程中直接记录需要的视图元素而不需要存储整个层级def getSideViewsOpt(root): if not root: return [], [] left_view, right_view [], [] queue deque([root]) while queue: level_size len(queue) for i in range(level_size): node queue.popleft() if i 0: left_view.append(node.val) if i level_size - 1: right_view.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return left_view, right_view优化后的版本空间复杂度从O(n)降到了O(w)其中w是树的最大宽度这在树非常不平衡时会有明显优势。4. 完整解决方案与LeetCode变种将上述模块组合起来我们得到完整的PTA天梯赛题目解法def solve(): import sys from collections import deque # 读取输入 n int(sys.stdin.readline()) inorder list(map(int, sys.stdin.readline().split())) postorder list(map(int, sys.stdin.readline().split())) # 建树 inorder_map {val:idx for idx, val in enumerate(inorder)} def buildTree(in_start, in_end, post_start, post_end): if in_start in_end: return None root_val postorder[post_end] root TreeNode(root_val) root_pos inorder_map[root_val] left_size root_pos - in_start root.left buildTree(in_start, root_pos-1, post_start, post_startleft_size-1) root.right buildTree(root_pos1, in_end, post_startleft_size, post_end-1) return root root buildTree(0, n-1, 0, n-1) # 获取侧视图 left_view, right_view [], [] queue deque([root]) while queue: level_size len(queue) for i in range(level_size): node queue.popleft() if i 0: left_view.append(node.val) if i level_size - 1: right_view.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) # 格式化输出 print(R:, .join(map(str, right_view))) print(L:, .join(map(str, left_view))) solve()在LeetCode 199题二叉树的右视图中只需要输出右视图解法可以更简洁def rightSideView(root): if not root: return [] result [] queue [root] while queue: level_size len(queue) for i in range(level_size): node queue.pop(0) if i level_size - 1: result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result类似的变种题还包括LeetCode 199. 二叉树的右视图LeetCode 314. 二叉树的垂直遍历LeetCode 637. 二叉树的层平均值掌握核心的层序遍历技巧后这些题目都能迎刃而解。5. 面试中的常见考察点与避坑指南在实际面试中面试官可能会从以下几个角度深入考察递归与迭代的选择递归实现简洁但可能有栈溢出风险迭代实现更可控但代码稍复杂边界条件处理空树情况单节点树完全倾斜的树如只有左子树复杂度分析时间复杂度的详细推导空间复杂度的优化空间测试用例设计正常情况边缘情况大规模数据测试常见错误包括建树时索引计算错误层序遍历时忘记记录层级大小没有处理空输入的情况视图元素提取逻辑错误建议在实现时先写出明确的注释再填充代码最后用简单测试用例验证# 测试用例1正常二叉树 # 1 # / \ # 2 3 # / \ # 4 5 inorder [4, 2, 5, 1, 3] postorder [4, 5, 2, 3, 1] # 预期输出 # R: 1 3 5 # L: 1 2 4 # 测试用例2只有左子树 # 1 # / # 2 # / # 3 inorder [3, 2, 1] postorder [3, 2, 1] # 预期输出 # R: 1 2 3 # L: 1 2 36. 举一反三从二叉树侧视图到更复杂的树问题掌握了二叉树侧视图的解法后我们可以扩展到更复杂的树遍历问题锯齿形层序遍历奇数层从左到右偶数层从右到左def zigzagLevelOrder(root): if not root: return [] result [] queue deque([root]) left_to_right True while queue: level_size len(queue) current_level deque() for _ in range(level_size): node queue.popleft() if left_to_right: current_level.append(node.val) else: current_level.appendleft(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(list(current_level)) left_to_right not left_to_right return result垂直遍历按列输出节点相同位置的节点按从上到下顺序def verticalOrder(root): if not root: return [] column_table defaultdict(list) queue deque([(root, 0)]) min_col max_col 0 while queue: node, col queue.popleft() column_table[col].append(node.val) min_col min(min_col, col) max_col max(max_col, col) if node.left: queue.append((node.left, col - 1)) if node.right: queue.append((node.right, col 1)) return [column_table[col] for col in range(min_col, max_col 1)]边界遍历左边界、叶子节点、右边界逆时针方向输出def boundaryOfBinaryTree(root): if not root: return [] result [root.val] def leftBoundary(node): if not node or (not node.left and not node.right): return result.append(node.val) if node.left: leftBoundary(node.left) else: leftBoundary(node.right) def leaves(node): if not node: return if not node.left and not node.right: result.append(node.val) return leaves(node.left) leaves(node.right) def rightBoundary(node): if not node or (not node.left and not node.right): return if node.right: rightBoundary(node.right) else: rightBoundary(node.left) result.append(node.val) leftBoundary(root.left) leaves(root.left) leaves(root.right) rightBoundary(root.right) return result这些扩展问题都建立在基本的树遍历技巧之上通过不同的视角处理节点间的相对位置关系。