document.write('本题可以通过对二叉树进行后序遍历来解决，具体思路如下：
对于当前遍历到的结点root，假设已经求出在遍历root结点前最大的路径和为max：
(1)求出以root.left为起始结点，叶子结点为终结点的最大路径和为maxLeft；
(2)同理求出以root.right为起始结点，叶子结点为终结点的最大路径和maxRight。
包含root结点的最长路径可能包含如下三种情况：
(1)leftMax=root.val+maxLeft(左子树最大路径和可能为负)。
(2)rightMax=root.val+maxRight(右子树最大路径和可能为负)。
(3)allMax=root.val+maxLeft+maxRight(左右子树的最大路径和都不为负)。
因此，包含root结点的最大路径和为tmpMax=max(leftMax,rightMax,allMax)。
在求出包含root结点的最大路径后，如果tmpMax＞max，那么更新最大路径和为tmpMax。
实现代码如下：
class TreeNode:
def __init__(self,val):
self.val=val
self.left=None
self.right=None
class IntRef:
def __init__(self):
self.val=None
#求a,b,c的最大值
def Max(a,b,c):
maxs=a if a＞b else b
maxs=maxs if maxs＞c else C
return maxs
#寻找最长路径
def findMaxPathRecursive(root,maxs):
if None==root:
return 0
else:
#求左子树以root.left为起始结点的最大路径和
sumLeft=findMaxPathRecursive(root.left,maxs)
#求右子树以root.right为起始结点的最大路径和
sumRight=findMaxPathRecursive(root.right,maxs)
#求以root为起始结点, 叶子结点为结束结点的最大路径和
allMax=root.val+sumLeft+sumRight
leftMax=root.val+sumLeft
rightMax=root.val+sumRight
tmpMax=Max(allMax, leftMax, rightMax)
if tmpMax＞maxs.val:
maxs.val=tmpMax
subMax=sumLeft if sumLeft＞sumRight else sumRight
#返回以root为起始结点, 叶子结点为结束结点的最大路径和
return root.val+subMax
def findMaxPath(root):
maxs=IntRef()
maxs.val=-2**31
findMaxPathRecursive(root,maxs)
return maxs.val
if __name__=="__main__":
root=TreeNode(2)
left=TreeNode(3)
right=TreeNode(5)
root.left=left
root.right=right
print findMaxPath(root)
程序的运行结果为
10
算法性能分析：
二叉树后序遍历的时间复杂度为O(N)，因此，这种方法的时间复杂度也为O(N)。
');