第四周 Leetcode 124. Binary Tree Maximum Path Sum （HARD）

题意：给定一个二叉树，每个节点有一个权值，寻找任意一个路径，使得权值和最大，只需返回权值和。

思路：对于每一个节点首先考虑以这个节点为结尾（包含它或者不包含）的最大值，有两种情况，分别来自左儿子和右儿子设为Vnow。

然后考虑经过这个节点的情况来更新最终答案。更新答案后返回Vnow供父节点继续更新。

代码很简单.

有一个类似的很有趣的题目，给定一个二叉树，选择一条路径，使得权值最大的和最小的相差最大。参考POJ3728

class Solution {

public:

    int ans;

	Solution(){ans=-2147483647;}

    int maxPathSum(TreeNode* root) {

       solve(root);

       return ans;

    }

    int solve(TreeNode* root) {

       if(root->left==NULL&&root->right==NULL)

       	{ans=max(ans,root->val);return root->val;}

	   int vnow=root->val;ans=max(ans,vnow);

	   int lv=0,rv=0;

	   if(root->left!=NULL)

	   		{

	   		 lv=solve(root->left);

	   		 vnow=max(vnow,root->val+lv);

	   		 ans=max(ans,vnow);

			}

	   if(root->right!=NULL)

	   		{

	   		 rv=solve(root->right);

	   		 vnow=max(vnow,root->val+rv);

	   		 ans=max(ans,vnow);

			}

	    ans=max(ans,lv+rv+root->val);

	    return vnow;

    }

};

巴特西

第四周 Leetcode 124. Binary Tree Maximum Path Sum （HARD）

最新文章

热门文章