首页 > 代码库 > 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 3Return 6.
思路：题目要求求解最大的路径和：我们先只考虑以node为根的子树，显然必定包含node的最大和路径为；{ node }、{ subPath(node->left), node }、{ node, subPath(node->right) }、{ subPath(node->left), node, subPath(node->right) }四个中值最大的那条路径。因此，我们只需求出subPath(node->left)和subPath(node->right)，即可确定必定包含node的最大和路径。显然，问题的规模变小了。
我们再来考虑node的父节点。显然，为了确定必定包含node父节点的最大和路径，subPath(node)应返回：{ node }、{ subPath(node->left), node }、{ node, subPath(node->right) }三个中值最大的那条路径的值。
该问题本质上是二叉树的后序遍历。我们使用递归可以获得非常优雅的解法。同时我们需要使用一个全局变量存储找到的最大路径和。
1 class Solution { 2 public: 3 int maxPathSum( TreeNode *root ) { 4 if( !root ) { return 0; } 5 maxSum = root->val; 6 maxPathSumSub( root ); 7 return maxSum; 8 } 9 private:10 int maxPathSumSub( TreeNode *node ) {11 int left = 0, right = 0;12 if( node->left ) { left = maxPathSumSub( node->left ); }13 if( node->right ) { right = maxPathSumSub( node->right ); }14 int curMax = node->val + max( 0, left ) + max( 0, right );15 if( maxSum < curMax ) { maxSum = curMax; }16 return node->val + max( 0, max( left, right ) );17 }18 int maxSum;19 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。