问题一：二叉树任意两个叶子间简单路径最大和
示例：
-100
/ \
2 100
/ \
10 20
思路：这个问题适用于递归思路。
首先，将问题简单化：假设包含最大和summax的简单路径经过结点A，结点A必然存在左右子树，设f(node*)函数可以求出子树叶子到子树树根最大和路径，则有summax=A.val+f(A.leftchild)+f(A.rightchild)，此时，遍历树中拥有左右子树的节点，并提取最大值即可。
再假设fmax(node*)可以求出以该结点参数为根的树/子树的任意两个叶子间简单路径最大和，则可以分为三种情况：1.最大和路径经过根结点；2.最大和路径在左子树中；3.最大和路径在右子树中。比较三者取出最大值作为fmax函数的返回值。
为了简化代码，使用之前所写的创建二叉树的函数
struct tree_node;
struct tree_node{
struct tree_node *lc;
struct tree_node *rc;
int data;
};
typedef struct tree_node treenode; void pre_create_tree(treenode **T){ //递归法
int datatemp; fflush(stdin);
scanf("%d", &datatemp); if(datatemp==-1000){
*T=NULL;
}
else{
if((*T=(treenode*)malloc(sizeof(treenode)))==NULL){
exit(0);
}
else{
(*T)->data=datatemp;
(*T)->lc = (*T)->rc = NULL;
pre_create_tree(&(*T)->lc);
pre_create_tree(&(*T)->rc);
}
}
} void pre_visit_tree(treenode *T){ //递归法
if(T!=NULL){
printf("%d ", T->data);
pre_visit_tree(T->lc);
pre_visit_tree(T->rc);
}
else{
return;
}
}
这里为了方便，假设输入数据不等于-1000，那么求叶子到树根最大值函数f(node*)如下所示：
int maxpath(treenode *T){
int templc=-100000,temprc=-1000000;
if(T==NULL)
return INT_MIN;
if(T->lc==NULL&&T->rc==NULL)
return T->data;
if(T->lc!=NULL)
templc = T->data+maxpath(T->lc);
if(T->rc!=NULL)
temprc = T->data+maxpath(T->rc);
if(templc>temprc)
return templc;
else
return temprc;
}
求解任意叶子简单路径最大和fmax函数实现：
int maxs(treenode *T){
int temproot=0,templc=0, temprc=0;
if(T==NULL)
return INT_MIN;
if(T->lc==NULL||T->rc==NULL){
return INT_MIN;
}
if(T->lc!=NULL&&T->rc!=NULL){
temproot=maxpath(T->lc)+maxpath(T->rc)+T->data;
}
templc = maxs(T->lc);
temprc = maxs(T->rc);
if(temproot>templc)
if(temproot>temprc)
return temproot;
else
return temprc;
else
if(templc>temprc)
return templc;
else
return temprc;
}
测试输入：-100 2 10 -1000 -1000 20 -1000 -1000 100
调用maxs函数将返回32。
问题二：我们将问题稍微变化一下，改为求任意结点间简单路径最大和，允许路径只有一个结点。
这时候递归是否有效？答案是肯定的。
看图：
a
/ \
b c
/ \ / \
bl br cl cr
把树或者子树看成上图的模式，假设我们已经实现一个函数f(node* param)，根结点为参数结点param的子树，经过param结点的最大路径和(这里并不需要到达叶子)。
由上图我们对一个结点分3种情况考虑：
1.最大和路径经过结点a，即有四种可能值：a.val，a.val+f(b)，a.val+f(c)，a.val+f(b)+f(c)；
2.最大和路径不经过结点a，且在结点a的左子树内并经过结点b，值为f(b)；
3.最大和路径不经过结点a，且在结点a的右子树内并经过结点c，值为f(c)。(情况2,3是不是不需要呢？好像是的，先记着后面来改)
在这六种可能值中，取其最大值作为计算经过结点a的最大值的“可能路径”，然后遍历树中结点即可得到最大数值。
int maxpath2(treenode *T){
int templc=0,temprc=0;
if(T==NULL)
return -100000;
if(T->lc==NULL&&T->rc==NULL)
return T->data;
if(T->lc!=NULL)
templc = maxpath2(T->lc);
if(T->rc!=NULL)
temprc = maxpath2(T->rc);
if(templc<=0&&temprc<=0){
return T->data;
}
else if(templc>temprc)
return T->data+templc;
else
return T->data+temprc;
}
int maxs2(treenode *T){
long int temproot=0,templc=0,temprc=0;
long int sum[6],max,k;
if(T==NULL)
return -100000;
if(T->lc==NULL&&T->rc==NULL)
return T->data;
memset(sum, 0, sizeof(int)*6);
sum[0] = T->data;
sum[1] = maxpath2(T->lc);
sum[2] = maxpath2(T->rc);
sum[3] = T->data+sum[1];
//sum[4] = T->data+sum[2];
//sum[5] = T->data+sum[1]+sum[2];
for(k=1, temproot=sum[0]; k<4; k++){
if(sum[k]>temproot)
temproot = sum[k];
}
templc = maxs2(T->lc);
temprc = maxs2(T->rc);
if(temproot>templc&&temproot>temprc)
return temproot;
else if(templc>temprc)
return templc;
else
return temprc;
}
那么我们试试以下面的二叉树为例
-100
/ \
2 100
/ \
10 -20
输入为-100 2 10 -1000 -1000 -20 -1000 -1000 100 -1000 -1000
调用maxs2结果就应该为100了（不是12）。