int: ">
题目标题

输出二叉树的最大路径和的路径。

参考解析
  1. class Solution:
  2. def __init__(self): # 定义一个result属性
  3. self.result = float("-inf")
  4. def maxPathSum(self, root: TreeNode) -> int:
  5. if root == None:
  6. return 0
  7. self.getMax(root)
  8. return self.result
  9. def getMax(self,root): # 定义一个辅助函数
  10. if root == None: # 如果当前节点为空就表示包含当前节点的最大路径为0
  11. return 0
  12. # 递归的计算当前节点的左子树和右子树能提供的最大路径和,如果为负,就置为零(和0比较)
  13. left = max(0,self.getMax(root.left))
  14. right = max(0,self.getMax(root.right))
  15. # 每计算一次左右子树的最大值,就更新当前的result
  16. self.result = max(self.result,left + right + root.val)
  17. # 往父节点回溯的话,最大路径就不能同时包含左右两个子树,
  18. # 因此需要用左右子树较大的那个子树加上当前节点的值进行回溯
  19. return max(left,right) + root.val
  20. #(递归函数,返回的是回溯需要的式子,而不是返回最终结果(比如这里的 return result))