题目描述
Given a binary tree, find the maximum path sum.
给出一棵二叉树，计算其最大路径和。
The path may start and end at any node in the tree.
路径的起止结点必须位于树内。
For example:
例如：
Given the below binary tree,
给出如下二叉树:
1
/ \
2 3
Return 6.
返回6（sum path 2-1-3）
解题思路
假设，我们正在处理的子树的根结点root一定位于这个path内，我们计算当path一定经过了root时的最大路径和max(root)。
那么max(root)该如何计算呢？
我们假设我们已经求除了当path一定经过root->left时的最大路径和max(root->left)，也求除了当path一定经过root->right时的最大路径和max(root->right)，这时候，如果max(root->left)>0，那么对于root而言，将root->left和root连接起来的path的和一定比root自己构成的path的和要大；
同理，如果max(root->right)>0，那么对于root而言，将root->left和root连接起来的path的和一定比root自己构成的path的和要大。
然而对于一条路径来说，
root要么跟root->left连接在一起，
要么跟root->right连接在一起.
因此我们需要对
root->data+max(root->left)
root->data
root->data +max(root->right)
求出其中的最大值来作为max(root)的值。
有了如上的步骤之后，我们到底该如何确定二叉树的最大路径和呢？
实际上，我们上述过程是求得了以某一个结点为根的子树的最大路径和，其中路径的起点为根，终点为子树中的某一结点，我们注意到这个过程中，我们每次都只是从根的左右子结点中选择其中的一个来连接到path中，实际上，一个path是有可能既连接root->left，又连接root->right的，但是这种情况至多会出现在其中一个结点x上，否则就会出现路径的分叉了。
因此，我们在求的max(root->left)、max(root->right)之后，尝试将root作为我们上面提到的x点，然后来计算由max(root->left)、max(root->right)、root->val可能构成的最大和tmp，然后判定tmp和当前缓存好的max（最大路径和），并更新max值即可。
最后，这个max就是我们要求的最大路径和。
算法
1.如果root为NULL，返回0
2.递归调用1-5，求得maxSum(root->left)和maxSum(root->right)
3.maxSum(root) = max(root->data, root->data + maxSum(root->left), root->data + maxSum(root->right))
4.判定root->val 、 maxSum(root->left)、maxSum(root->right)三者可能构成的最大和（必须包含root->data），是否大于目前缓存的最大路径和tmp，如果是则更新tmp
5.返回maxSum(root)的值
6.递归调用结束后，tmp的值就是最大路径和
代码实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MaxLen 15
//定义节点
typedef struct node
{
struct node *lchild;
struct node *rchild;
int data;
} BitNode, *BiTree;
//*BiTree的意思是给 struct node*起了个别名，叫BiTree，故BiTree为指向节点的指针。
void printArray(int arr[],int length)
{
for (int i = 0; i<length; i++) {
printf(" %d",arr[i]);
}
printf("\n");
}
BiTree creatBTree(int data[],int index,int n)
{
BiTree pNode = NULL;
if(index < n && (data[index]!=0)) //数组中-1 表示该节点为空
{
pNode = (BitNode *)malloc(sizeof(BitNode));
if(pNode == NULL)
return NULL;
pNode->data = data[index];
pNode->lchild = creatBTree(data, 2 * index + 1, n); //将二叉树按照层序遍历, 依次标序号, 从0开始
pNode->rchild = creatBTree(data, 2 * index + 2, n);
}
return pNode;
}
//先序遍历
void PreOrder(BiTree p)
{
if(p != NULL)
{
printf(" %d",p->data); //输出该结点
PreOrder(p->lchild); //遍历左子树
PreOrder(p->rchild); //遍历右子树
}
else
{
printf(" #");
}
}
/* 求两个数中较大的数字 */
int max(int arg1, int arg2)
{ return arg1 > arg2 ? arg1 : arg2; }
/* 求3个数中较大的数字 */
int maxThree(int arg1, int arg2, int arg3)
{ return max(arg1, max(arg2, arg3)); }
/**
* 计算二叉树子树的最大路径和以及整棵二叉树的最大路径和
* 子树路径必须以根结点开始，以树中某一结点结束
* 二叉树的最大路径和的路径，不必以根结点为开始结点
* @param root 二叉树根结点
* @param tmpMax 暂存整棵二叉树的最路径和的变量的地址
* @return 子树的最大路径和
*/
int maxChildPathSum(BiTree root, int *tmpMax)
{
if (root == NULL)
{
//printf("\n");
return 0;
}
else
{
// printf("%d ",root->data);
}
/* 计算左右子树的最大路径和 */
int leftMax = maxChildPathSum(root->lchild, tmpMax);
int rightMax = maxChildPathSum(root->rchild, tmpMax);
/* 尝试更新整棵二叉树的最大路径和 */
int tmp = root->data;
if (leftMax > 0)
{
tmp += leftMax;
}
if (rightMax > 0)
{
tmp += rightMax;
}
if (tmp > *tmpMax)
{
*tmpMax = tmp;
}
/* 计算并返回子树的最大路径和 */
int maxRoot = maxThree(root->data,root->data+leftMax, root->data+rightMax);
return maxRoot;
}
/**
* 计算二叉树的最大路径和
* @param root 二叉树根结点
* @return 最大路径和
*/
int maxPathSum(BiTree root)
{
if (root == NULL) return 0;
int tmpMax = root->data;
maxChildPathSum(root, &tmpMax);
return tmpMax;
}
int main(int argc, const char * argv[]) {
int arr[MaxLen] ;
srand( (unsigned)time( NULL ) );
for (int i = 0; i<MaxLen; i++)
{
arr[i] = rand()%30+1-15;
}
printf("原始数组：\n");
printArray(arr, MaxLen);
BiTree tree = creatBTree(arr, 0, MaxLen);
printf("先序遍历：\n");
PreOrder(tree);
printf("\n");
printf("\n");
printf("最大路径和=%d\n",maxPathSum(tree));
printf("\n");
// printf("先序遍历：\n");
//PreOrder(tree);
// printf("\n");
return 0;
}
运行结果
原始数组：
7 -9 -10 -8 6 1 -12 5 10 4 4 -6 11 -4 -6
先序遍历：
7 -9 -8 5 # # 10 # # 6 4 # # 4 # # -10 1 -6 # # 11 # # -12 -4 # # -6 # #
最大路径和=14
Program ended with exit code: 0
