首页 > 代码库 > 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.
求二叉树的最大路径和，路径可以从任一节点开始到任一节点结束。要注意节点值可以为负。
这题可以用分治法递归实现。我们可以把问题拆分开：最后的最大路径必然有一个“最高点”，因此我们只要针对所有结点，求出：如果路径把这个节点作为“最高点”，路径最长可达多少？记为max，然后在max中求出最大值MAX即为所求结果。
代码如下：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int maxPathSum(TreeNode* root) { rec(root); return max; } int rec(TreeNode *root) { if(root == NULL) return 0; int l = rec(root->left); int r = rec(root->right); if(root->val>max) max = root->val; if(root->val+l>max) max = root->val+l; if(root->val+r>max) max = root->val+r; if(root->val+l+r > max) max = root->val+l+r; int maxReturn = root->val>(root->val+l) ? root->val:root->val+l; return (root->val+r)>maxReturn ? root->val+r : maxReturn; }private: int max = INT_MIN;};
rec的返回值为max(root->val,root->val+r,root->val+l)。这是因为要和上层结点连成一条路径。
leetcode -124. Binary Tree Maximum Path Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。