leetcode題目鏈接

題目描述

Given a binary tree, find the maximum path sum.
給出一棵二叉樹(shù)，計(jì)算其最大路徑和。
The path may start and end at any node in the tree.
路徑的起止結(jié)點(diǎn)必須位于樹(shù)內(nèi)。
For example:
例如：
Given the below binary tree,
給出如下二叉樹(shù):

   1
  / \
 2   3

Return 6.
返回6（sum path 2-1-3）

解題思路

假設(shè)，我們正在處理的子樹(shù)的根結(jié)點(diǎn)root一定位于這個(gè)path內(nèi)，我們計(jì)算當(dāng)path一定經(jīng)過(guò)了root時(shí)的最大路徑和max(root)。
那么max(root)該如何計(jì)算呢？
我們假設(shè)我們已經(jīng)求除了當(dāng)path一定經(jīng)過(guò)root->left時(shí)的最大路徑和max(root->left)，也求除了當(dāng)path一定經(jīng)過(guò)root->right時(shí)的最大路徑和max(root->right)，這時(shí)候，如果max(root->left)>0，那么對(duì)于root而言，將root->left和root連接起來(lái)的path的和一定比root自己構(gòu)成的path的和要大；
同理，如果max(root->right)>0，那么對(duì)于root而言，將root->left和root連接起來(lái)的path的和一定比root自己構(gòu)成的path的和要大。
然而對(duì)于一條路徑來(lái)說(shuō)，
root要么跟root->left連接在一起，
要么跟root->right連接在一起.

因此我們需要對(duì)
root->data+max(root->left)
root->data
root->data +max(root->right)
求出其中的最大值來(lái)作為max(root)的值。

有了如上的步驟之后，我們到底該如何確定二叉樹(shù)的最大路徑和呢？
實(shí)際上，我們上述過(guò)程是求得了以某一個(gè)結(jié)點(diǎn)為根的子樹(shù)的最大路徑和，其中路徑的起點(diǎn)為根，終點(diǎn)為子樹(shù)中的某一結(jié)點(diǎn)，我們注意到這個(gè)過(guò)程中，我們每次都只是從根的左右子結(jié)點(diǎn)中選擇其中的一個(gè)來(lái)連接到path中，實(shí)際上，一個(gè)path是有可能既連接root->left，又連接root->right的，但是這種情況至多會(huì)出現(xiàn)在其中一個(gè)結(jié)點(diǎn)x上，否則就會(huì)出現(xiàn)路徑的分叉了。
因此，我們?cè)谇蟮膍ax(root->left)、max(root->right)之后，嘗試將root作為我們上面提到的x點(diǎn)，然后來(lái)計(jì)算由max(root->left)、max(root->right)、root->val可能構(gòu)成的最大和tmp，然后判定tmp和當(dāng)前緩存好的max（最大路徑和），并更新max值即可。
最后，這個(gè)max就是我們要求的最大路徑和。

算法

1.如果root為NULL，返回0

2.遞歸調(diào)用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)三者可能構(gòu)成的最大和（必須包含root->data），是否大于目前緩存的最大路徑和tmp，如果是則更新tmp

5.返回maxSum(root)的值

6.遞歸調(diào)用結(jié)束后，tmp的值就是最大路徑和

代碼實(shí)現(xiàn)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MaxLen 15

//定義節(jié)點(diǎn)
typedef struct node
{
    struct node *lchild;
    struct node *rchild;
    int data;
} BitNode, *BiTree;
//*BiTree的意思是給 struct node*起了個(gè)別名，叫BiTree，故BiTree為指向節(jié)點(diǎn)的指針。


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))  //數(shù)組中-1 表示該節(jié)點(diǎn)為空
    {
        pNode = (BitNode *)malloc(sizeof(BitNode));
        if(pNode == NULL)
            return NULL;
        pNode->data = data[index];
        pNode->lchild = creatBTree(data, 2 * index + 1, n);  //將二叉樹(shù)按照層序遍歷, 依次標(biāo)序號(hào), 從0開(kāi)始
        pNode->rchild = creatBTree(data, 2 * index + 2, n);
    }
    
    return pNode;
}

//先序遍歷
void PreOrder(BiTree p)
{
    if(p != NULL)
    {
        printf(" %d",p->data);      //輸出該結(jié)點(diǎn)
        PreOrder(p->lchild);  //遍歷左子樹(shù)
        PreOrder(p->rchild); //遍歷右子樹(shù)
    }
    else
    {
        printf(" #");
    }
}

/* 求兩個(gè)數(shù)中較大的數(shù)字 */
int max(int arg1, int arg2)
{ return arg1 > arg2 ? arg1 : arg2; }

/* 求3個(gè)數(shù)中較大的數(shù)字 */
int maxThree(int arg1, int arg2, int arg3)
{ return max(arg1, max(arg2, arg3)); }


/**
 * 計(jì)算二叉樹(shù)子樹(shù)的最大路徑和以及整棵二叉樹(shù)的最大路徑和
 * 子樹(shù)路徑必須以根結(jié)點(diǎn)開(kāi)始，以樹(shù)中某一結(jié)點(diǎn)結(jié)束
 * 二叉樹(shù)的最大路徑和的路徑，不必以根結(jié)點(diǎn)為開(kāi)始結(jié)點(diǎn)
 * @param root 二叉樹(shù)根結(jié)點(diǎn)
 * @param tmpMax 暫存整棵二叉樹(shù)的最路徑和的變量的地址
 * @return 子樹(shù)的最大路徑和
 */
int maxChildPathSum(BiTree root, int *tmpMax)
{
    
    if (root == NULL)
    {
        //printf("\n");
        return 0;
    }
    else
    {
       // printf("%d ",root->data);
    }
  
    /* 計(jì)算左右子樹(shù)的最大路徑和 */
    int leftMax = maxChildPathSum(root->lchild, tmpMax);
    int rightMax = maxChildPathSum(root->rchild, tmpMax);
    
    /* 嘗試更新整棵二叉樹(shù)的最大路徑和 */
    int tmp = root->data;
   
    if (leftMax > 0)
    {
        tmp += leftMax;
        
    }
    if (rightMax > 0)
    {
        tmp += rightMax;
        
    }
    
  
    
    if (tmp > *tmpMax)
    {
        *tmpMax = tmp;
        
    }
    
    /* 計(jì)算并返回子樹(shù)的最大路徑和 */
    int maxRoot = maxThree(root->data,root->data+leftMax, root->data+rightMax);
    
    return maxRoot;
}

/**
 * 計(jì)算二叉樹(shù)的最大路徑和
 * @param  root 二叉樹(shù)根結(jié)點(diǎn)
 * @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("原始數(shù)組：\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;
}

運(yùn)行結(jié)果

可視化二叉樹(shù)

原始數(shù)組：
 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

最大路徑和.png