CodeBrick 博客

Appearance

2014·41 二叉树 WPL：一遍遍历带上深度，直观写法即满分 ​

本文属于「从暴力解到最优解」专题的第二组。第一组讲的是「怎么把暴力解优化掉」；第二组反过来，讲怎么认出一道题根本不用优化——直观写法就是满分解，力气要花在别的地方。

题目 ​

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

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

其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 T 的根结点的指针，请设计求 T 的 WPL 的算法。要求：(1) 给出算法的基本设计思想；(2) 使用 C 或 C++ 语言，给出二叉树结点的数据类型定义；(3) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。总分 13 分。

先注意一件事：题面没有出现「尽可能高效」。按总纲的分类，这属于第二组——没有悬在头顶的最优性要求。但这不等于随便写，下面会看到力气该花在哪。

直观解法：DFS 带着深度走一遍 ​

WPL 的定义已经把算法框架写在题面里了：「所有叶结点的带权路径长度之和」。一个叶结点的「路径长度」就是它到根的边数，也就是它的深度（根深度记为 0）。于是最自然的想法是：递归遍历整棵树，把「当前深度」当参数一路往下传，到叶子就把 weight × depth 记一笔账，内部结点不产生贡献（题面明确「叶结点的 weight 域保存权值」）。

c
typedef struct TreeNode {
    struct TreeNode *left;
    int              weight;     /* 叶结点的权值 */
    struct TreeNode *right;
} TreeNode;

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×深度 */
    }

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

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

复杂度：每个结点只访问一次，时间 O(n)；递归栈深等于树高，空间 O(h)。

为什么它就是满分解 ​

这道题没有「暴力 vs 最优」的分差，因为这个 O(n) 已经是下界，无法再降。用总纲的「找浪费三问」审一遍：

  1. 有没有重复扫描？ 没有。每个结点只在自己那一层被访问一次，深度是顺路传下去的，不需要事后再补算。
  2. 有没有重算已知的东西？ 没有。每个结点的深度、每个叶子的贡献都只算一次，算完直接累加进返回值，没有任何值需要重复推导。
  3. 有没有放着性质不用？ 没有。题目没给额外的结构性质（比如有序性）可利用，「遍历一遍」就是解题需要的全部信息。

更根本的一条：WPL 定义在「所有叶结点」之上，要拿到每个叶结点的权值和深度，就必须至少访问树中每一个结点一次——这是 O(n) 的理论下界，任何正确算法都躲不开。既然碰到了下界，直观写法就是最优解。

这也是第二组题的共同特征：当问题定义本身要求"看过每一个结点"时，"优化"这个动作根本不存在。认出这一点，你就不会在考场上为不存在的分数去冒险写复杂代码。

真正的难点在三处细节 ​

分不在优化上，那在哪？在这道题最容易失手的三处易错细节：

  • 叶结点判定必须是 && 不是 ||：叶子的定义是「左右孩子都空」，只有 node->left == NULL && node->right == NULL 同时成立才算叶子。写成 || 会把度为 1 的中间结点也误判成叶子，提前返回、少递归一层，WPL 直接算错。
  • 根深度必须从 0 起：题面说的是「路径长度」，即边数，根到自己是 0 条边。如果 wplDfs(root, 0) 误写成 wplDfs(root, 1)，每个叶子的深度都多算 1，整个 WPL 系统性偏大。
  • 内部结点的 weight 不计入：题面白纸黑字写着「叶结点的 weight 域保存该结点的权值」——言下之意，非叶结点的 weight 是不保证有意义的、不能读也不能用。代码里只在叶子分支读取 node->weight，内部结点分支完全不碰这个字段，这一点比看起来更容易被忽略。

三处任何一处出错，代码依然「跑得动」、不会崩溃，但算出来的 WPL 就是错的——这正是它们比空指针段错误更隐蔽、更容易在考场上被忽略的原因。

DFS 带深度求 WPL，看一遍 ​

构造一棵四叶子的树：根 → 叶(10, 深度 1)；根 → 内部 → 叶(6, 深度 2)；再往下一层内部 → 叶(4, 深度 3)、叶(8, 深度 3)。手算 WPL = 10×1 + 6×2 + 4×3 + 8×3 = 10+12+12+24 = 58。

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足 ​

第二组题的另一半功夫，是忍住不去做多余的事。这道题最容易出现的两个「过度设计」陷阱：

  • 把求 WPL 和求树高的模板混用。求树高是「自底向上」的写法——递归先拿到左右子树的高度，再返回 max(h1, h2) + 1，深度信息在回溯的路上才产生；求 WPL 恰恰相反，是「自顶向下」——深度是从根开始一路往下传的参数，到叶子才用得上。这是两种不同的递归范式，一旦在考场上把两者的框架拼在一起（比如先递归求出高度、再想办法用高度反推每个叶子的深度），代码会绕出很多不必要的复杂度，还容易把 weight 和 h 两类变量搞混。
  • 改用 BFS + 队列显式维护深度。这确实能算对，但队列里要么塞 (结点指针, 深度) 的二元组，要么额外开一个深度数组，空间也是 O(n)，比递归的 O(h) 更费——递归本身就在用调用栈免费维护深度，没必要自己重新发明一套。

看到「求和 + 遍历」就本能地想套用别的模板凑复杂度分析，反而容易在改造模板的过程中出错。这道题最稳的做法就是把 DFS 自顶向下传 depth 的框架原样写出来，不做多余的变形。

下一步 ​

相关真题（1题）

2016Q42综合题8分
去刷题

正则 k 叉树性质：已知非叶结点数 m 求叶结点数、已知高度 h 求结点数范围

树与森林