首页 > 代码库 > 第四周 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。