【二叉树遍历】leetcode -- 127 最大路径和

资源汇总

链接
画二叉树示意图网站

思路

利用后序遍历，先把左子树右子树的路径和求出来，如果左右子树的和小于等于0，则当成0相加。

代码

import sys

class Solution:
    def __init__(self):
        self.maxSum = -sys.maxsize-1

    def maxPathSum(self, root: TreeNode) -> int:
        
        self.oneSideMax(root)

        return self.maxSum

    def oneSideMax(self, root):
        if root is None:
            return 0

        leftSum = max(0, self.oneSideMax(root.left))
        rightSum = max(0, self.oneSideMax(root.right))

        self.maxSum = max(self.maxSum, leftSum+rightSum+root.val)

        # 因为只能选择一路，要么是左到拫，要么是右到根
        return max(leftSum, rightSum) + root.val

为什么向上返回的和是 return max(leftSum, rightSum) + root.val

因为对于在第二层的 节点2 中，向上返回的值为 max(leftSum, rightSum) + root.val 意味着当前节点要被考虑到，当前节点要被考虑到的话只有两条路径，3->2 或者 0->2，要选路径和最大的值返回，显然是 max() + root.val