1. 二叉树高度与宽度的基础概念二叉树的高度就像我们测量一栋楼有多少层。从地面根节点开始算起每往下一层就加一。空树高度为0只有根节点的树高度为1。实际项目中这个指标能帮我们判断数据库索引的查询效率——B树的高度直接影响磁盘I/O次数。二叉树的宽度则是找出最拥挤的那一层有多少个节点。想象高峰期的地铁宽度就是最繁忙时段的车厢人数。在UI布局系统中这决定了控件需要的最小水平空间。比如计算文件系统目录树的最大子目录数时宽度就非常实用。我用一个实际案例说明某次优化文件系统扫描工具时发现递归太深的目录会爆栈。通过计算高度我们改用层序遍历避免递归而宽度数据则帮我们合理设置了内存缓冲区大小。2. 层序遍历解法详解2.1 层序遍历计算高度层序遍历就像消防员逐层搜救用队列Queue这个先进先出的工具最合适。以下是Python实现from collections import deque def tree_height(root): if not root: return 0 height 0 queue deque([root]) while queue: level_size len(queue) # 关键点锁定当前层节点数 for _ in range(level_size): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) height 1 # 处理完一层就长高 return height调试技巧在循环里打印队列内容我常用print([n.val for n in queue])观察处理过程。曾经踩过的坑是忘记判空遇到None节点还继续操作导致崩溃。2.2 层序遍历计算宽度计算宽度需要统计每层的人口密度。改进下高度代码def tree_width(root): if not root: return 0 max_width 0 queue deque([root]) while queue: level_size len(queue) max_width max(max_width, level_size) # 记录峰值 for _ in range(level_size): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return max_width性能对比测试百万节点平衡树时层序遍历的O(n)时间复杂度表现稳定。但要注意队列的内存消耗极端情况下可能达到O(n)空间复杂度。3. 递归解法深度解析3.1 递归计算高度递归思路像信任链每个节点只关心自己的高度子节点的高度交给它们自己报告。数学表达式为height(node) 1 max(height(left), height(right))Java实现示例int getHeight(TreeNode node) { if (node null) return 0; return 1 Math.max(getHeight(node.left), getHeight(node.right)); }常见误区新手常忘记1导致高度少算一层。有次代码审查发现同事写成return Math.max(left, right)导致所有结果偏小。递归虽然简洁但要注意基线条件空节点返回0和递归条件。3.2 递归计算宽度递归求宽度稍微复杂些需要记录每层的节点数。可以用HashMap统计def widthOfTree(root): level_counts {} def traverse(node, level): if not node: return level_counts[level] level_counts.get(level, 0) 1 traverse(node.left, level 1) traverse(node.right, level 1) traverse(root, 0) return max(level_counts.values()) if level_counts else 0递归的局限当树高度很大时比如10万层Python默认递归深度会爆栈。这时候还是得用层序遍历这种迭代方法。4. 方法对比与实战选择时间复杂度两种方法都是O(n)每个节点访问一次。但递归有隐性的调用栈开销。空间对比层序遍历显式使用队列最坏空间O(n)完全二叉树最后一层递归的栈空间消耗在平衡树中是O(log n)但斜树会退化为O(n)选择建议面试优先写递归简洁不易错生产环境大数据量用迭代避免栈溢出需要即时中断时选迭代比如找到目标就退出我在实际项目中的选择策略处理用户家谱树通常20层用递归处理机器学习决策树可能上千层用迭代。曾经处理过一个推荐系统的决策树递归改迭代后性能提升37%。
