首页 > 代码库 > 【LeetCode】Binary Tree Maximum Path Sum
【LeetCode】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.
树结构显然用递归来解，解题关键：
1、对于每一层递归，只有包含此层树根节点的值才可以返回到上层。否则路径将不连续。
2、返回的值最多为根节点加上左右子树中的一个返回值，而不能加上两个返回值。否则路径将分叉。
在这两个前提下有个需要注意的问题，最上层返回的值并不一定是满足要求的最大值，
因为最大值对应的路径不一定包含root的值，可能存在于某个子树上。
因此解决方案为设置全局变量maxSum，在递归过程中不断更新最大值。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int maxSum; Solution() { maxSum = INT_MIN; } int maxPathSum(TreeNode *root) { Helper(root); return maxSum; } int Helper(TreeNode *root) {//return the maxSum containing root //if the maxSum without root is the true answer, update the maxSum directly if(root == NULL) return 0; else if(root->left == NULL && root->right == NULL) { //no child, return the root->val and maybe update the maxSum maxSum = (maxSum >= root->val) ? maxSum : root->val; return root->val; } else if(root->left != NULL && root->right == NULL) { int left = Helper(root->left); //return value must contain root->val //if left <= 0, drop it int tmp = root->val+max(0,left); maxSum = (maxSum >= tmp) ? maxSum : tmp; return tmp; } else if(root->left == NULL && root->right != NULL) { int right = Helper(root->right); //return value must contain root->val //if right <= 0, drop it int tmp = root->val+max(0,right); maxSum = (maxSum >= tmp) ? maxSum : tmp; return tmp; } else { int left = Helper(root->left); int right = Helper(root->right); //if left or right <= 0, drop it int tmp = root->val+max(0,left)+max(0,right); maxSum = (maxSum >= tmp) ? maxSum : tmp; //attention here! return value contain at most one child return root->val+max(0, max(left,right)); } }};
【LeetCode】Binary Tree Maximum Path Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。