二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为:
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求:
⑴ 给出算法的基本设计思想;
⑵ 使用C或C++语言,给出二叉树结点的数据类型定义;
⑶ 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
本题为一道简单难度的考察搜索的算法...
用户登录可进行刷题及查看答案
本题为一道简单难度的考察搜索的算法题,考研只需要掌握深度优先搜索和广度优先搜索即可。
这道题要注意的是题目要求“二叉树中所有叶结点的带权路径长度之和”,也就是只有“叶结点”才需要计算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;
}
复杂度分析
方法二:广度优先搜索
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;
}
复杂度分析
登录后提交答案
暂无评论,来抢沙发