首页 > 代码库 > 第四周 Leetcode 124. Binary Tree Maximum Path Sum (HARD)

第四周 Leetcode 124. Binary Tree Maximum Path Sum (HARD)

124. Binary Tree Maximum Path Sum

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

思路:对于每一个节点 首先考虑以这个节点为结尾(包含它或者不包含)的最大值,有两种情况,分别来自左儿子和右儿子设为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)