题目

二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 T，采用二叉链表存储，结点结构为：

+--------+--------+--------+
| left   | weight | right  |
+--------+--------+--------+

其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 T 的根结点的指针，请设计求 T 的 WPL 的算法。要求：

(1) 给出算法的基本设计思想。

(2) 使用 C 或 C++ 语言，给出二叉树结点的数据类型定义。

(3) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

解析

(1) 设计思想

答案：递归遍历二叉树，传递当前结点的深度 depth；遇到叶结点时累加 weight × depth，遇到内部结点则递归左右子树（depth+1）。

为什么这种 DFS 就能算 WPL？

WPL（Weighted Path Length）= 所有叶子的（权值 × 路径长度）之和。每个叶子的"路径长度"就是从根到该叶子的边数（也即该叶子的深度，根定为深度 0）。一次 DFS 自然地把"深度"作为递归参数向下传递：

• 进入新结点 depth+1；
• 到达叶子时（左右孩子都为 NULL）：贡献 node->weight × depth；
• 内部结点不贡献——题面明确"叶结点的 weight 域保存权值"，内部结点的 weight 不计入 WPL。

实现细节：

1. 主函数调用一次 wplDfs(root, 0)，根的深度从 0 开始；
2. 递归函数判断：
   • node == NULL → return 0；
   • 是叶子（左右子树都空）→ return weight × depth；
   • 否则 → return 左子树 WPL + 右子树 WPL。

(2) 二叉树结点的数据类型定义

typedef struct TreeNode {
    struct TreeNode *left;         // 左孩子指针
    int              weight;       // 叶结点的权值
    struct TreeNode *right;        // 右孩子指针
} TreeNode;

字段顺序对照题面给的结构图（left | weight | right）。weight 在内部结点不使用，但所有结点共用同一类型，便于树的统一构造与遍历。

(3) 代码实现

static int wplDfs(TreeNode *node, int depth) {
    if (node == NULL) return 0;                   // 空树或空指针：贡献 0

    // 判断叶结点（左右子树都为 NULL）
    if (node->left == NULL && node->right == NULL) {
        return node->weight * depth;              // 叶子：贡献 weight × 深度
    }

    // 内部结点：递归累加左右子树的 WPL，深度 +1
    return wplDfs(node->left,  depth + 1)
         + wplDfs(node->right, depth + 1);
}

int wpl(TreeNode *root) {
    return wplDfs(root, 0);                       // 根的深度从 0 起算
}

关键点说明：

• 叶子判定 = 左右孩子都 NULL：本题二叉链表，没有"度为 1 的中间结点"作为叶子——题面默认"叶 = 左右都空"。如果是表达式树等会出现"单孩子结点"的场景，要按题意单独判。
• 根的深度从 0 起：题中"路径长度"指边数，根到自己 0 条边。如果题目改成"层数从 1 起"，把初始 depth 改 1 即可，递归形态不变。
• 递归 vs 迭代：本题用递归最自然；用迭代（BFS + 队列携带深度）也能实现，但代码繁、空间也是 O(n)，不划算。
• 复杂度：时间 O(n)，每个结点访问一次；空间 O(h)，递归栈深 = 树高。最坏（退化链状树）h = n，平均（平衡树）h = log n。

编者注（生僻术语）：WPL 是哈夫曼编码的核心评价指标。哈夫曼树就是"在所有叶子权值固定的二叉树中 WPL 最小的那棵"。本题不要求构造最优树，只要求会算 WPL——即对任意给定二叉树（可能根本不是哈夫曼树），按定义遍历求和。