2014 年第 41 题

题目描述

给定一棵二叉树，叶结点上存放非负权值。请计算该二叉树的带权路径长度 WPL。

定义：

• 结点的路径长度：从根到该结点所经过的边数。
• 二叉树的带权路径长度：所有叶结点的“权值 × 路径长度”之和。

解题思路

直接用深度优先遍历。

递归到每个结点时，顺便记录当前深度 depth：

• 若当前结点是叶结点，则把 node.weight * depth 加入答案。
• 若不是叶结点，则继续递归左右子树。

这题本质不难，关键是定义不能搞错：只有叶结点参与计算。

手算示例

        A
      /   \
     B     C
    / \     \
   D   E     F

D 权值 3，深度 2，贡献 3 * 2 = 6
E 权值 5，深度 2，贡献 5 * 2 = 10
F 权值 2，深度 2，贡献 2 * 2 = 4

WPL = 6 + 10 + 4 = 20

Python 实现

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


def weighted_path_length(root):
    def dfs(node, depth):
        if node is None:
            return 0
        if node.left is None and node.right is None:
            return node.weight * depth
        return dfs(node.left, depth + 1) + dfs(node.right, depth + 1)

    return dfs(root, 0)

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(h)，h 为树高

易错点

• 只有叶结点计入 WPL。
• 路径长度按边数算，不是按结点数算。
• 根结点深度是 0，不是 1。

对应题

来源	题目	相似度	主要差异
PAT 甲级	1053 Path of Equal Weight	60%	该题更偏路径枚举，真题是直接求 WPL

难度

⭐️⭐️⭐️