考研笔记

板子：带深度参数的递归——WPL（2014）

WPL 是所有叶子的「权值 路径长度」之和。深度作为参数往下传（前序的思路），走到叶子就把「权值 深度」交上来。

代码

int wplDfs(BiTree T, int depth) {            // depth：T 到根的路径长度（边数），根为 0
    if (T == NULL) return 0;
    if (T->lchild == NULL && T->rchild == NULL)
        return T->data * depth;              // 叶子：权值 × 路径长度
    return wplDfs(T->lchild, depth + 1) + wplDfs(T->rchild, depth + 1);   // 孩子比自己深一层
}
 
int WPL(BiTree root) {
    return wplDfs(root, 0);                  // 根的路径长度是 0
}
 
int WPL2(BiTree root) {                      // 另一种解法：层序遍历，按层处理
    BiTNode *q[MaxSize];
    int front = 0, rear = 0, depth = 0, wpl = 0;
    if (root != NULL) q[rear++] = root;
    while (front < rear) {
        int cnt = rear - front;              // 当前这一层的结点数
        while (cnt-- > 0) {
            BiTNode *p = q[front++];
            if (p->lchild == NULL && p->rchild == NULL) wpl += p->data * depth;   // 叶子才累加
            if (p->lchild != NULL) q[rear++] = p->lchild;
            if (p->rchild != NULL) q[rear++] = p->rchild;
        }
        depth++;                             // 这一层处理完，深度 +1
    }
    return wpl;
}

复杂度：两种解法都是时间 ；递归解法空间 ，层序解法空间 。

例：根有两个孩子，左孩子下面挂着权值为 2、3 的两个叶子，右孩子是权值为 5 的叶子。WPL 。

考场答案要点（2014）

  • 原题的结点字段是 left | weight | right。考场上把 data 换成 weight、把 lchild / rchild 换成 left / right。
  • （1）设计思想：先序遍历二叉树，用参数 depth 记录当前结点的深度（根为 0）。遇到叶子，就把「权值 深度」累加到结果中；非叶结点把 depth + 1 传给左右孩子。
  • （3）复杂度：每个结点访问一次，时间 ；递归栈深度为树高，空间 。

关键边界

  • 路径长度是边数：根的路径长度是 0，所以要从 wplDfs(root, 0) 开始。如果习惯让根在第 1 层，叶子就要乘 depth - 1。
  • 只累加叶子。原题中只有叶子的 weight 有意义，非叶结点的权值不算。

易错点

  • 也可以用全局变量或 static 变量累加。这种写法没问题，但多次调用前要记得清零。
  • 手算哈夫曼树时有个捷径：WPL 等于所有非叶结点的权值之和（每个非叶结点的权值是它两个孩子之和）。见 5.5 哈夫曼树与并查集。

链接

反向链接