首页 > 代码库 > 【Lintcode】094.Binary Tree Maximum Path Sum
【Lintcode】094.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.
Example
Given the below binary tree:
1
/ 2 3
return 6
.
题解:
Solution 1 () from here
class Solution { public: int maxPathSum(TreeNode *root) { if (root == NULL) { return 0; } int res = INT_MIN; helper(root, res); return res; } int helper(TreeNode *root, int &res) { if (root == NULL) { return 0; } int sum = root->val; int leftMax = helper(root->left, res); int rightMax = helper(root->right, res); if (leftMax > 0) { sum += leftMax; } if (rightMax > 0) { sum += rightMax; } res = max(sum, res); return max(0, max(leftMax, rightMax)) + root->val; } };
【Lintcode】094.Binary Tree Maximum Path Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。