问题 D: DS二叉树--二叉树之最大路径

题目描述

给定一颗二叉树的逻辑结构（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构

二叉树的每个结点都有一个权值，从根结点到每个叶子结点将形成一条路径，每条路径的权值等于路径上所有结点的权值和。编程求出二叉树的最大路径权值。如下图所示，共有4个叶子即有4条路径，

路径1权值=5 + 4 + 11 + 7 = 27 路径2权值=5 + 4 + 11 + 2 = 22

路径3权值=5 + 8 + 13 = 26 路径4权值=5 + 8 + 4 + 1 = 18

可计算出最大路径权值是27。

该树输入的先序遍历结果为ABCD00E000FG00H0I00，各结点权值为：

A-5，B-4，C-11，D-7，E-2，F-8，G-13，H-4，I-1

输入

第一行输入一个整数t，表示有t个测试数据

第二行输入一棵二叉树的先序遍历，每个结点用字母表示

第三行先输入n表示二叉树的结点数量，然后输入每个结点的权值，权值顺序与前面结点输入顺序对应

以此类推输入下一棵二叉树

输出

每行输出每棵二叉树的最大路径权值，如果最大路径权值有重复，只输出1个

样例输入

2

AB0C00D00

4 5 3 2 6

ABCD00E000FG00H0I00

9 5 4 11 7 2 8 13 4 1

样例输出

11

27

提示

代码

#include
using namespace std;
class TreeNode{
public:
TreeNode* leftChild;//左孩子
TreeNoderightChild;//右孩子
int weight;//该节点的权重
TreeNode(){
leftChild= NULL;
rightChild= NULL;
weight= 0;
}
};
class Tree{
private:
int maxx;//记录最大的权重
int pos;//字母表的位置
int pos_wt;//字母表对应的权重的位置
int n;
TreeNode root;//根节点
string str;
int weight;
TreeNode createTree(){//递归建树
TreeNode* t;
char ch= str[pos++];

if(ch== '0')
t= NULL;
else{
t= new TreeNode();
t->weight= weight[pos_wt++];
t->leftChild= createTree();
t->rightChild= createTree();
}
return t;
}
void PreOrder(TreeNode *root){//先序遍历的同时将父节点的权重加到左右孩 //子上
if(root){
if(root->leftChild&&root->rightChild){//左右孩子都有
root->leftChild->weight+= root->weight;
root->rightChild->weight+= root->weight;
}
else if(root->leftChild)//只有左孩子
root->leftChild->weight+= root->weight;
else if(root->rightChild)//只有右孩子
root->rightChild->weight+= root->weight;

maxx= maxx> root->weight? maxx: root->weight;
PreOrder(root->leftChild);
PreOrder(root->rightChild);
}
}
public:
void createTree(string st, int wt[], int nn){
str= st;
maxx= -10000;
pos= 0;
pos_wt= 0;
n= nn;
weight= new int[n+ 5];
for(int i= 0; i< n; i++)
weight[i]= wt[i];
root= createTree();
}
void getMax(){
PreOrder(root);
cout<<maxx<<endl;
}
};
int main(){
int t;
cin>>t;
while(t--){
string str;
cin>>str;
int n;
cin>>n;
int *array= new int[n+ 5];
for(int i= 0; i< n; i++)
cin>>array[i];

Tree tree;
tree.createTree(str, array, n);
tree.getMax();
}
return 0;
}