leetcode 124. Binary Tree Maximum Path Sum

谁践踏了优雅 2022-07-26 12:23 135阅读 0赞

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;
    	}
    };

[Center]: /images/20220724/946dc5a1e99d4beaa87c856c8cf0e668.png