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

返回主页

[数据结构 P2082] 二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表

学习人数: 488

正确率: 100%

答案解析

题目描述

未通过

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

\[
\begin{array}{|c|c|c|}
\hline
\texttt{left} & \texttt{weight} & \texttt{right} \\
\hline
\end{array}
\]

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

⑴ 给出算法的基本设计思想；（3分）

⑵ 使用C或C++语言，给出二叉树结点的数据类型定义；（8分）

⑶ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（2分）

上一题

下一题

加入错题本

个人笔记

已有1条笔记

登录后提交答案

暂无评论，来抢沙发

参考答案

本题为一道简单难度的考察搜索的算法...

用户登录可进行刷题及查看答案

本题为一道简单难度的考察搜索的算法题，考研只需要掌握深度优先搜索和广度优先搜索即可。

这道题要注意的是题目要求“二叉树中所有叶结点的带权路径长度之和”，也就是只有“叶结点”才需要计算WPL。

构造测试用例如下图所示：

方法一：深度优先搜索

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int weight;
    struct TreeNode *left;
    struct TreeNode *right;
};

int dfs(struct TreeNode* root, int depth) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return root->weight * depth;
    }
    return dfs(root->left, depth + 1) + dfs(root->right, depth + 1);
}

int pathSum(struct TreeNode* root) {
    return dfs(root, 0);
}

struct TreeNode *createBinaryTree(int *a, int n) {
    if (a[0] == -1) {
        return NULL;
    }
    int i = 0;
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->weight = a[i++];
    root->left = NULL;
    root->right = NULL;
    struct TreeNode** que = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    struct TreeNode *curr = root;
    que[rear++] = curr;
    while (front < rear && i < n) {
        curr = que[front++];
        for (int j = 0; j < 2 && i < n; j++, i++) {
            if (a[i] != -1) {
                if (j == 0) {
                    curr->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
                    curr->left->weight = a[i];
                    curr->left->left = NULL;
                    curr->left->right = NULL;
                    que[rear++] = curr->left;
                } else {
                    curr->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
                    curr->right->weight = a[i];
                    curr->right->left = NULL;
                    curr->right->right = NULL;
                    que[rear++] = curr->right;
                }
            }
        }
    }
    return root;
}

int main() {
    int W[] = {1, -1, 2, 3};
    printf("%d", pathSum(createBinaryTree(W, 4)));
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int weight;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : weight(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : weight(x), left(nullptr), right(nullptr) {}
};

int dfs(TreeNode* root, int depth) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return root->weight * depth;
    }
    return dfs(root->left, depth + 1) + dfs(root->right, depth + 1);
}

int pathSum(TreeNode* root) {
    return dfs(root, 0);
}

TreeNode *createBinaryTree(vector<int> weights) {
    if (weights[0] == -1) {
        return nullptr;
    }
    const int n = weights.size();
    int i = 0;
    TreeNode *root = new TreeNode(weights[i++]);
    queue<TreeNode *> Q;
    Q.push(root);
    while (!Q.empty() && i < n) {
        TreeNode *node = Q.front();
        Q.pop();
        for (int j = 0; j < 2 && i < n; j++, i++) {
            if (weights[i] != -1) {
                if (j == 0) {
                    node->left = new TreeNode(weights[i]);
                    Q.push(node->left);
                } else {
                    node->right = new TreeNode(weights[i]);
                    Q.push(node->right);
                }
            }
        }
    }
    return root;
}

int main() {
    vector<int> W = {1, -1, 2, 3};
    cout << pathSum(createBinaryTree(W));
    return 0;
}

复杂度分析

时间复杂度： O(n) ，其中 n 是二叉树的结点数。
空间复杂度： O(n) ，为递归过程中栈的开销，平均情况下为 O(log⁡n) ，最坏情况下树呈现链状，为 O(n) 。

方法二：广度优先搜索

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int weight;
    struct TreeNode *left;
    struct TreeNode *right;
};

int pathSum(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    struct TreeNode *curr = root;
    struct TreeNode** que = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    que[rear++] = curr;
    int wpl = 0;
    int depth = 0;
    while (front < rear) {
        int sz = rear - front;
        while (sz > 0) {
            curr = que[front++];
            if (curr->left == NULL && curr->right == NULL) {
                wpl += curr->weight * depth;
            }
            if (curr->left) {
                que[rear++] = curr->left;
            }
            if (curr->right) {
                que[rear++] = curr->right;
            }
            sz--;
        }
        depth++;
    }
    return wpl;
}

struct TreeNode *createBinaryTree(int *a, int n) {
    if (a[0] == -1) {
        return NULL;
    }
    int i = 0;
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->weight = a[i++];
    root->left = NULL;
    root->right = NULL;
    struct TreeNode** que = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    struct TreeNode *curr = root;
    que[rear++] = curr;
    while (front < rear && i < n) {
        curr = que[front++];
        for (int j = 0; j < 2 && i < n; j++, i++) {
            if (a[i] != -1) {
                if (j == 0) {
                    curr->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
                    curr->left->weight = a[i];
                    curr->left->left = NULL;
                    curr->left->right = NULL;
                    que[rear++] = curr->left;
                } else {
                    curr->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
                    curr->right->weight = a[i];
                    curr->right->left = NULL;
                    curr->right->right = NULL;
                    que[rear++] = curr->right;
                }
            }
        }
    }
    return root;
}

int main() {
    int W[] = {1, -1, 2, 3};
    printf("%d", pathSum(createBinaryTree(W, 4)));
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int weight;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : weight(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : weight(x), left(nullptr), right(nullptr) {}
};

int pathSum(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    queue<TreeNode *>Q;
    TreeNode *curr = root;
    Q.push(curr);
    int wpl = 0;
    int depth = 0;
    while (!Q.empty()) {
        int sz = (int)Q.size();
        while (sz > 0) {
            curr = Q.front();
            Q.pop();
            if (curr->left == nullptr && curr->right == nullptr) {
                wpl += curr->weight * depth;
            }
            if (curr->left) {
                Q.push(curr->left);
            }
            if (curr->right) {
                Q.push(curr->right);
            }
            sz--;
        }
        depth++;
    }
    return wpl;
}

TreeNode *createBinaryTree(vector<int> weights) {
    if (weights[0] == -1) {
        return nullptr;
    }
    const int n = weights.size();
    int i = 0;
    TreeNode *root = new TreeNode(weights[i++]);
    queue<TreeNode *> Q;
    Q.push(root);
    while (!Q.empty() && i < n) {
        TreeNode *node = Q.front();
        Q.pop();
        for (int j = 0; j < 2 && i < n; j++, i++) {
            if (weights[i] != -1) {
                if (j == 0) {
                    node->left = new TreeNode(weights[i]);
                    Q.push(node->left);
                } else {
                    node->right = new TreeNode(weights[i]);
                    Q.push(node->right);
                }
            }
        }
    }
    return root;
}

int main() {
    vector<int> W = {1, -1, 2, 3};
    cout << pathSum(createBinaryTree(W));
    return 0;
}

复杂度分析

时间复杂度： O(n) ，其中 n 是二叉树的结点数。
空间复杂度： O(n) ，队列中的元素不超过 n 个。