博客

7-13 二叉树路径和 (10 分)
编写程序找出二叉树中和最大的路径，二叉树结点为不等于0的整数。本题的“路径”限定为以根结点为起点，以叶结点为终点的路径。路径的和，即该路径所包含的所有结点的数据值之和。

输入格式:
输入为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列。

输出格式:
输出为两行，第一行为该二叉树路径和的最大值，第二行为一组整数，每个整数后一个空格，即该最大路径包含的结点值（按从根的叶的顺序），如果存在多条满足条件路径，则输出最左边一条。

输入样例1:
1 2 0 0 3 0 0
输出样例1:
4
1 3
输入样例2:
-1 2 0 0 3 0 0
输出样例2:
2
-1 3

#include<cstdio>   
#include<cstdlib>
#include<iostream>
#include<stack>
#include<climits>
int maxSum=INT_MIN;
using namespace std;
typedef struct Node
{
    int biao;//标记用的 
    int data;
    struct BiTNode *lchild,*rchild;
    Node(int x):data(x),biao(1),lchild(NULL),rchild(NULL){};
    
}BiTNode,*BiTree;

void CreateBiTree(BiTree T)
{
	int x;
	cin>>x;
	if(x==0){
		return NULL;
	}
	else{
		T=new Node(x);
		T->lchild=build(T->lchild);
		T->rchild=build(T->rchild);
	} 
	return T;
}


int maxGain(BiTree T) 
{
 	if(!T->lchild&&!T->rchild) return T->data;//到了叶节点，则返回该点的值 
 
	 int l=INT_MIN;//默认左 右子树的值最小 
	 int r=INT_MIN;
	 
	if(T->lchild){
		l=maxGain(T->lchild);//如果做不空，则找左最大的 
	}
	
	if(T->rchild){  //如果右不空，同理 
		r=maxGain(T->rchild);//接着值 
	}
	if(r>l) T->biao=0;//如果右大于左那默认走，标记为0，证明要走右边 
     
        return T->data+max(l,r);//返回  该点的值+max(l,r); 

  
}
    


void prin(BiTree T){
 while(T){
 	printf("%d ",T->data);
 	if(T->biao==0){  //biao为0，表示右大于左，所以走右子树 
 		T=T->rchild;
	 }
	 else 	T=T->lchild;//否则走左子树 
 }
}

int main(){
    BiTree T;
    CreateBiTree(T);   
   cout<<maxGain(T)<<endl;
    
 prin(T); 
 printf("\n");
    return 0;
}