leetcode 124. Binary Tree Maximum Path Sum-蒲公英云

leetcode 124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

1
      / \
     2   3

Return 6.

这题要理解题目意思，否则会提交很多次的。本身这题题目意思也不明确。

来张图说明一下：

Center

对于这个二叉树，最大路径如红线所示，怎么样，意思明白了吧。注意，路线不必经过root。

class Solution {
    struct TN
    {
        int sum;
        TN*left, *right;
        TN(int x) :sum(x){
            left = NULL, right = NULL;
        }
    };
    vector<vector<TN*>>allque;
public:
    ~Solution()
    {
        if (!allque.empty())
        for (int i = 0; i < allque[0].size(); i++)
            delete allque[0][i];
    }
    int maxPathSum(TreeNode* root) {
        if (root == NULL)
            return 0;
        if (root->left == NULL&&root->right == NULL)
            return root->val;
        vector<TreeNode*>que;
        que.push_back(root);
        TN*root1 = new TN(root->val);
        vector<TN*>que1;
        que1.push_back(root1);
        while (!que.empty())
        {
            vector<TreeNode*>newque;
            vector<TN*>newque1;
            for (int i = 0; i < que.size(); i++)
            {
                if (que[i]->left != NULL)
                {
                    TN*n = new TN(que[i]->left->val);
                    //n->parent = que1[i];
                    que1[i]->left = n;
                    newque.push_back(que[i]->left);
                    newque1.push_back(n);
                }
                if (que[i]->right != NULL)
                {
                    TN*n = new TN(que[i]->right->val);
                    //n->parent = que1[i];
                    que1[i]->right = n;
                    newque.push_back(que[i]->right);
                    newque1.push_back(n);
                }
            }
            allque.push_back(que1);
            que = newque;
            que1 = newque1;
        }
        int maxsum = -1000000000;
        int imax = allque.size() - 2;
        for (int i = imax; i >= 0; i--)
        {
            for (int j = 0; j < allque[i].size(); j++)
            {
                int ss = -1000000000;
                if (allque[i][j]->left != NULL)
                {
                    if (allque[i][j]->left->sum>maxsum)
                        maxsum = allque[i][j]->left->sum;
                    if (allque[i][j]->left->sum>ss)
                            ss = allque[i][j]->left->sum;
                }
                if (allque[i][j]->right != NULL)
                {
                    if (allque[i][j]->right->sum > maxsum)
                        maxsum = allque[i][j]->right->sum;
                    if (allque[i][j]->right->sum > ss)
                            ss = allque[i][j]->right->sum;
                }
                if (allque[i][j]->left != NULL&&allque[i][j]->right != NULL
                    &&allque[i][j]->right->sum > 0 && allque[i][j]->left->sum > 0)
                {
                    if (allque[i][j]->sum + allque[i][j]->right->sum + allque[i][j]->left->sum > maxsum)
                        maxsum = allque[i][j]->sum + allque[i][j]->right->sum + allque[i][j]->left->sum;
                }
                allque[i][j]->sum += (ss > 0 ? ss : 0);
                if (allque[i][j]->sum > maxsum)
                    maxsum = allque[i][j]->sum;
            }
            for (int j = 0; j < allque[i + 1].size(); j++)
                delete allque[i + 1][j];
            allque.pop_back();
        }
        return maxsum;
    }
};