java编程求二叉树最大路径问题代码分析
题目：
BinaryTreeMaximumPathSum
Givenabinarytree,findthemaximumpathsum.
Thepathmaystartandendatanynodeinthetree.
Forexample:
Giventhebelowbinarytree,
1 /\ 23
Return6.
节点可能为负数，寻找一条最路径使得所经过节点和最大。路径可以开始和结束于任何节点但是不能走回头路。
这道题虽然看起来不同寻常，但是想一下，可以发现不外乎二叉树的遍历+简单的动态规划思想。
我们可以把问题拆分开：即便最后的最大路径没有经过根节点，它必然也有自己的“最高点”，因此我们只要针对所有结点，求出：如果路径把这个节点作为“最高点”，路径最长可达多少？记为max。然后在max中求出最大值MAX即为所求结果。和“求整数序列中的最大连续子序列”一样思路。
下面就是找各个“最高点”对应的max之间的关系了。
我们拿根节点为例，对于经过根节点的最大路径的计算方式为：
我们找出左子树中以左孩子为起点的最大路径长度a，和右子树中以右孩子为起点的最大路径长度b。然后这个点的max=MAX(a+b+node.val,a+node.val,b+node.val,node.val)
因此我们定义一个函数来算上面的a或者b，它的参数是一个节点，它的返回值是最大路径长度，但是这个路径的起点必须是输入节点，而且路径必须在以起点为根节点的子树上。
那么函数func(node)的return值可以这样定义：returnMAX(func(node.left)+node.val,func(node.right)+node.val,node.val)
终止条件是node==null，直接返回0。
接着我们发现上述计算max和求出MAX的过程完全可以放到func(node)里去。
按照这个思路的代码，maxPathSumCore就是上面func(node)的实现：
/**
*Definitionforbinarytree
*structTreeNode{
*intval;
*TreeNode*left;
*TreeNode*right;
*TreeNode(intx):val(x),left(NULL),right(NULL){}
*};
*/
classSolution{
public:
intmaxPathSum(TreeNode*root){
maxPathSumCore(root);
returnMAX;
}
intmaxPathSumCore(TreeNode*node){
if(NULL==node)return0;
inta=maxPathSumCore(node->left);
intb=maxPathSumCore(node->right);
if((a+b+node->val)>MAX)MAX=(a+b+node->val);
if((a+node->val)>MAX)MAX=(a+node->val);
if((b+node->val)>MAX)MAX=(b+node->val);
if(node->val>MAX)MAX=node->val;
intmaxViaThisNode=((a+node->val)>node->val?(a+node->val):node->val);
return(maxViaThisNode>(b+node->val)?maxViaThisNode:(b+node->val));
}
private:
intMAX=-99999999;
}
;
时间复杂度O(n)，n为总节点数。
总结
以上就是本文关于java编程求二叉树最大路径问题代码分析的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！