二叉树层平均值算法解析：Python实现BFS与DFS双解法及职场思考

近日关于互联网大厂劳动合同违约金的讨论，再次引发了技术圈对职场权益的关注。高额的违约金条款，本质上是企业降低核心人才流动成本的一种制度设计。这提醒我们，在追求高薪与平台的同时，也需理性评估其中的绑定成本。职场是等价交换，入职前审阅合同细节至关重要。

换个角度，这种对“层次”和“平均值”的关注，与我们在处理数据结构时的思路不谋而合。下面，我们通过一道经典的「二叉树的层平均值」算法题，来探讨如何系统化、分层级地处理问题。这不仅是技术能力的体现，也是一种结构化思维的训练。

问题定义

给定一棵二叉树的根节点 root，要求返回一个列表，其中第 i 个元素是二叉树第 i 层所有节点的平均值。

示例思考：若某一层节点值为 [3, 9, 20]，则该层平均值为 (3+9+20) / 3 = 32 / 3 ≈ 10.67。

问题的核心在于：如何按层遍历二叉树并高效统计每层数据。

解法一：广度优先搜索 (BFS) - 队列实现

“按层处理”最直观的思路便是广度优先搜索。我们可以借助队列，将每一层的节点视为一个批次进行处理。

算法步骤：

1. 初始化一个队列，将根节点入队。
2. 当队列不为空时，进入循环：
   a. 获取当前队列长度，此即当前层的节点数量 level_size。
   b. 初始化当前层节点值之和 level_sum 为 0。
   c. 循环 level_size 次，每次从队列左侧弹出一个节点：
   • 将其值累加到 level_sum。
   • 将其非空的左、右子节点依次加入队列末尾（这构成了下一层的待处理节点）。
     d. 计算当前层平均值 level_sum / level_size，并加入结果列表。
3. 队列为空时，遍历结束，返回结果列表。

以下是使用 Python 实现的代码：

from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root:
            return []
        q = deque([root])
        ans = []
        while q:
            level_size = len(q)
            level_sum = 0
            for _ in range(level_size):
                node = q.popleft()
                level_sum += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(level_sum / level_size)
        return ans

复杂度分析：

• 时间复杂度 O(n)：每个节点恰好入队和出队各一次。
• 空间复杂度 O(n)：在最坏情况下（平衡二叉树），队列中同时存储的节点数约为 n/2，仍为 O(n) 级别。

解法二：深度优先搜索 (DFS) - 递归实现

除了横向的BFS，我们也可以通过DFS在纵向遍历时，通过记录层号来归类节点数据。

算法思路：

1. 定义两个全局列表（或在递归函数外可修改的列表）：
   • sums: 用于存储每一层的节点值之和。
   • counts: 用于存储每一层的节点个数。
2. 定义一个递归函数 dfs(node, level)：
   • 若节点为空，直接返回。
   • 若当前层号 level 等于 sums 的长度，说明是第一次到达该层，在 sums 和 counts 中追加初始值。
   • 否则，将当前节点值累加到 sums[level]，并将 counts[level] 加1。
   • 递归处理左子树 (level + 1) 和右子树 (level + 1)。
3. 从根节点 (level=0) 启动递归。
4. 遍历结束后，将 sums 和 counts 两个列表逐元素相除，得到最终的平均值列表。

代码实现如下：

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        sums = []
        counts = []
        def dfs(node: Optional[TreeNode], level: int) -> None:
            if not node:
                return
            if level == len(sums):
                sums.append(node.val)
                counts.append(1)
            else:
                sums[level] += node.val
                counts[level] += 1
            dfs(node.left, level + 1)
            dfs(node.right, level + 1)
        dfs(root, 0)
        return [sums[i] / counts[i] for i in range(len(sums))]

复杂度分析：

• 时间复杂度 O(n)：每个节点被访问一次。
• 空间复杂度 O(h)：递归栈的深度取决于二叉树的高度 h。在最坏情况（链表状树）下为 O(n)。

总结与延伸

本题是掌握二叉树层序遍历的经典入门题。BFS的队列解法模板化程度高，逻辑清晰，是解决此类“按层处理”问题的首选。DFS解法则展示了如何通过递归参数传递层信息，实现数据的归集。

无论是处理职场中的复杂条款，还是解决技术上的算法问题，拆解层次、聚焦当前层面、系统化分析和处理，都是通用的有效策略。理解了这个BFS模板，类似的问题如「二叉树的层序遍历」、「二叉树的锯齿形层序遍历」、「在每个树行中找最大值」等均可迎刃而解。