【leetcode】Binary Tree Maximum Path Sum (medium)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

找树的最大路径和注意路径可以从任意点起始和结束。

我发现我真的还挺擅长树的题目的，递归不难。就是因为有个需要比较的量（最大和），所以需要再写一个函数。

因为路径可以从任意点起始和结束，所以每次递归的时候左右子树小于等于0的就可以不管了。

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <stack>

using namespace std;

//Definition for binary tree

struct TreeNode {

     int val;

     TreeNode *left;

     TreeNode *right;

     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

    int maxPathSum(TreeNode *root){

        if(root == NULL)

        {

            return ;

        }

        int MaxPathSum = root->val; //赋的初值一定要小于等于最后的值

        maxPathSumCur(root, MaxPathSum);

        return MaxPathSum;

    }

    int maxPathSumCur(TreeNode *root, int& MaxPathSum) {

        if(root == NULL)

        {

            return ;

        }

        int lsum =  maxPathSumCur(root->left, MaxPathSum);

        int rsum = maxPathSumCur(root->right, MaxPathSum);

        int maxPathSumCurrent = root->val; //每次根的值一定要加上 左右子树的就加大于0的

        if(lsum > )

        {

            maxPathSumCurrent += lsum;

        }

        if(rsum > )

        {

            maxPathSumCurrent += rsum;

        }

        MaxPathSum = max(maxPathSumCurrent, MaxPathSum);

        return max(root->val, max(root->val + lsum, root->val +rsum)); //返回时返回根 节点加左 或右子树 或单独根节点中最大的

    }

    void create(TreeNode *& root)

    {

        int d;

        scanf("%d", &d);

        if(d != )

        {

            root = new TreeNode(d);

            create(root->left);

            create(root->right);

        }

    }

};

int main()

{

    Solution s;

    TreeNode * T = NULL;

    s.create(T);

    int sum = s.maxPathSum(T);

    return ;

}