这题给了一棵二叉树叶结点里存着非负权值要计算它的带权路径长度也就是WPL。先把这个名字放到一边。我们实际要做的是找到每个叶子看从根到它走了几条边再用这个数乘它的权值最后加起来。比如一个叶子的权值是3从根到它要走两条边它就给答案贡献3×26。那在程序里怎么把这两个数同时拿到走到叶子时已经走了多远权值好找就在结点里。但原题的结点没有一个字段告诉我们它离根有多远。我的第一直觉是从根往下走。每走过一条边路径长度就加1这样到叶子时也就知道距离了。这里容易想得复杂要算路径长度是不是得把从根到这里的整条路径留下来其实先看我们要用它干什么。最后只要边的数量不需要知道路上经过了哪些结点。那就用一个数记着根是0走到孩子是1再走一层是2。这个数可以跟着递归一起传。函数多收一个depth表示从原来的根走到当前结点已经走了多少条边。调用孩子时传depth1。这里加的是走向孩子的那条边不是给答案随便加1。先拿一棵小树走走这棵树的左孩子直接是叶子权值2右孩子还不是叶子它下面有两个叶子权值3和4根 / \ 2 内部结点 / \ 3 4我们从根开始depth为0。先走左边。走了一条边到权值2的叶子depth是1。它的贡献就是2×12。再看右边。从根到右孩子也只走了一条边所以这里的depth同样是1。但它还不是叶子暂时不用它的weight计算答案要继续往下。再走一条边到3depth变成2贡献3×26到4时也经过两条边贡献4×28。三个叶子都算到了把2、6、8加起来答案是16。注意右边这个内部结点我们不是漏算了它而是WPL的定义只把叶子的贡献加进去。它的作用是让我们继续走到下面的两个叶子。算出来的2、6、8放到哪里一个直接的做法是准备一个sum每到一个叶子就把刚算出的乘积加进去。这样可以做。但我们已经在用递归了能不能顺便让函数把算出的结果交回来而不是另外维护全局sum先看最简单的叶子。到了2它下面没有其他结点了直接返回2。到了3返回6到了4返回8。那右边的内部结点拿到什么它拿到左孩子交回来的6又拿到右孩子交回来的8。它把这两份加起来返回14。这里可以停在右边这一次调用看。它自己的depth是1告诉两个孩子的depth都是2。但孩子交回来的是6和8不是两个2。我们传给函数的参数与函数最后返回的值是不同的东西。调用孩子时写depth1也不会把当前这一层的depth改成2。当前调用仍记着自己在深度1两个孩子分别拿到一份值为2的参数。这样从左孩子回来再算右孩子右孩子仍从同一个父深度加1不会越算越深。根结点就更好办了左边交回来2右边交回来14根返回16。把刚才这几次调用和返回放在一起看当前调用depth返回结果权值2的叶子12×1返回2权值3的叶子23×2返回6权值4的叶子24×2返回8右边内部结点168返回14根0214返回16这里可以分开理解我们去找孩子时多告诉它一个depth孩子算完以后交回来的是答案贡献不是depth。也不要在算右子树时重新把深度归零。它仍是原来那棵树的一部分从原根到右孩子已经走过的那条边不能丢掉。同样根接到右边的14以后也不用再给它加1。14已经是按原根到叶子的完整边数算出的68向下时增加的是深度向上时只相加贡献不能把这两个动作混起来。现在再写这个递归函数走完上面的例子函数需要做的事就具体了。如果当前结点为空下面没有东西返回0。如果当前结点是叶子权值和depth都已经拿到了返回它们的乘积。否则分别让左右孩子计算。它们的depth比当前多1等拿到两边结果就相加返回。#include stddef.h typedef struct BiNode { int weight; struct BiNode *left, *right; } BiNode; long long wplFrom(BiNode *node, int depth) { if (node NULL) return 0; // 只有叶结点的权值计入 WPL if (node-left NULL node-right NULL) return (long long)node-weight * depth; return wplFrom(node-left, depth 1) wplFrom(node-right, depth 1); } long long WPL(BiNode *root) { return wplFrom(root, 0); }上面的return wplFrom(...) wplFrom(...)就是表里内部结点做的事。两次调用都沿用当前depth再加1它们交回来的值才是加号两边的数。左右子树先算哪边不影响这里的和每个孩子都会在自己的调用里完成计算返回后父结点再得到结果。叶子判断要同时看左右孩子都为空。只有一边为空的结点仍然要继续算另一边空的那边返回0不会干扰答案。我当时排除层序遍历排除早了我一开始觉得既然要从根往叶子走那应该用DFS层序遍历不行。但现在回头看我们真正需要的是到达叶子时能拿到深度不是必须按某一种顺序到达。层序遍历也能做。最直接就是队列里不仅放结点还放它的depth取出当前结点发现是叶子就累加乘积不是叶子就把孩子和depth1入队。也可以一层一层处理先记住当前队列有多少个结点只取完这一层再把层数加1。不能一边入队下一层一边把新孩子也算作本层。所以这次我们用递归是因为它接得上刚才的思路不代表层序方法不能解这道题。最后补两个小情况。整棵树只有一个结点时它既是根也是叶子但从根到自己没有经过任何边乘积为0。空树则直接返回0。每个结点只访问一次时间O(n)。递归还要占调用栈空间是O(h)h为树高一条链那样的树最坏会到O(n)不能只数函数里几个变量就写O(1)。代码先转成long long再乘避免乘法先在int里进行最终总和仍须在long long范围内。树特别深时也要考虑递归栈限制。题意按2014年408原卷第41题整理原卷来自厦门工学院公开备考资料。下面保留我的解题复盘C实现与验证是补充不是官方答案。附录完整验证程序参照不递归传深度而是沿数组父下标反向数边再把叶子贡献相加。单结点和内部结点大权值也检查。完整程序包含上面的题解函数和独立参照。保留源码是为了读者能自己改输入、定位错误不需要先读完它才能理解正文。gcc -stdc11 -Wall -Wextra -Werror -pedantic -fsanitizeaddress,undefined -fno-omit-frame-pointer lab.c -o lab ./lab#include assert.h #include limits.h #include stdbool.h #include stddef.h #include stdio.h #include stdlib.h typedef struct BiNode { int weight; struct BiNode *left, *right; } BiNode; long long wplFrom(BiNode *node, int depth) { if (node NULL) return 0; // 只有叶结点的权值计入 WPL if (node-left NULL node-right NULL) return (long long)node-weight * depth; return wplFrom(node-left, depth 1) wplFrom(node-right, depth 1); } long long WPL(BiNode *root) { return wplFrom(root, 0); } unsigned rng_state 4082014; unsigned rnd(void) { rng_state rng_state * 1664525u 1013904223u; return rng_state; } int main(void) { size_t cases 0; assert(WPL(NULL) 0); for (int trial 0; trial 6000; trial) { BiNode nodes[127]; int present[127] {0}; present[0] 1; for (int i 1; i 127; i) present[i] present[(i - 1) / 2] (rnd() % 4 ! 0); for (int i 0; i 127; i) { nodes[i].weight (int)(rnd() % 100000); nodes[i].left 2 * i 1 127 present[2 * i 1] ? nodes[2 * i 1] : NULL; nodes[i].right 2 * i 2 127 present[2 * i 2] ? nodes[2 * i 2] : NULL; } long long expected 0; for (int i 0; i 127; i) if (present[i] !nodes[i].left !nodes[i].right) { int depth 0; for (int j i; j 0; j (j - 1) / 2) depth; expected (long long)nodes[i].weight * depth; } assert(WPL(nodes) expected); cases; } BiNode leaf {INT_MAX, NULL, NULL}, root {INT_MAX, leaf, NULL}; assert(WPL(leaf) 0); assert(WPL(root) INT_MAX); printf(PASS wpl cases%zu\n, cases); return 0; }这次改写后重新以严格编译选项和AddressSanitizer、UndefinedBehaviorSanitizer运行了上面的完整C程序6000组树形与叶子贡献检查通过输出如下。题解代码与此前版本逐字相同。assert不能通过-DNDEBUG关闭。PASS wpl cases6000有限测试是发现错误的证据不代替正文的正确性与复杂度理由。