首页 > 代码库 > Binary Tree Maximum Path Sum
Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1 / 2 3
Return 6.
算法：（有点动态规划的思想）首先明确要自底向上进行计算，只考虑当前节点root，我们从子节点向上返回的是一条线路目前的最大值，该线路最高层（最上面）的节点是该子节点，并且该子节点不能同时有左右分支（即在线路上不能同时有左右分支，如果有分支，root返回到上一节点后，不能形成一个链，会在root出现分叉），然后我们比较root->val,
root->val+leftMax(从左子树返回的值)，root->val+rightMax(从右子树返回的值)，其中最大的就是root节点应该向上返回的值，我们在计算root节点的返回值时，可以顺便计算以root为最高层节点的链的线路最大值（可以有分叉），只要比较，root->val, leftMax+root->val, root->val+rightMax, leftMax+rightMax+root->val,其中最大的就是以root为最高层次节点的线路的最大值，然后用这个最大值，和最初保存的最大值result(初始化为INT_MIN)做比较，如果大于result，更新result,最终result就是结果，代码如下，时间复杂度O(n)，只需要遍历一边二叉树（后序遍历）：
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 int result; 13 int maxPathSum(TreeNode *root) {14 result=INT_MIN;15 getMax(root);16 return result;17 }18 int getMax(TreeNode* root)19 {20 if(root==NULL) return 0;21 int leftMax=getMax(root->left);22 int rightMax=getMax(root->right);23 int tmax=max(max(leftMax+root->val,max(rightMax+root->val,root->val)),leftMax+rightMax+root->val);24 if(tmax>result) result=tmax;25 int rootmax=max(root->val,max(root->val+leftMax,root->val+rightMax));26 return rootmax;27 }28 };
Binary Tree Maximum Path Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。