124. 二叉树中的最大路径和

Difficulty
Hard
Tags
二叉树
URL
https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
Star
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
notion imagenotion image
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
notion imagenotion image
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
  • 树中节点数目范围是 [1, 3 * 104]
  • 1000 <= Node.val <= 1000
通过次数127,016提交次数290,009

法1 递归

思路
最大路径和：根据当前节点的角色，路径和可分为两种情况：
  • 一：以当前节点为根节点
    • 1.只有当前节点
    • 2.当前节点+左子树
    • 3.当前节点+右子书
    • 4.当前节点+左右子树
      • 这四种情况的最大值即为以当前节点为根的最大路径和。此最大值要和已经保存的最大值比较，得到整个树的最大路径值
  • 二：当前节点作为父节点的一个子节点和父节点连接的话则需取【单端的最大值】
      1. 只有当前节点
      1. 当前节点+左子树
      1. 当前节点+右子书 这三种情况的最大值
思路2
把树想象成一颗只有根节点、一个左子节点和一个右子节点的小树。然后大树由一颗颗小树构成。所以递归只需要考虑小树 以及 如何将小树和大树连接起来（一般通过返回值连接）
按照题意：一棵小树的结果可能有如下几个情况：
  1. 根节点
  1. 跟+左子节点
  1. 跟+右子节点
  1. 跟+左+右
  1. 左
  1. 右
如上六种情况，只有1 2 3 情况可以和别的树连接，即只有1 2 3 的结果需要返回。那么定义一个全局变量来统计1 2 3 4 5 6中最大的值，然后将1 3 4 的最大的值返回给父节点
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.res = None

    def maxPathSum(self, root: TreeNode) -> int:
        self.dfs(root)
        return self.res

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

        leftVal = self.dfs(root.left)
        rightVal = self.dfs(root.right)

        val_1 = root.val
        val_2 = root.val + leftVal
        val_3 = root.val + rightVal
        val_4 = root.val + leftVal + rightVal
        
        #当前遍历树的最大值
        if self.res is None:
            self.res = root.val
        self.res = max([self.res, val_1, val_2, val_3, val_4])
        #要和父节点关联，则需要取去除情况4的最大值
        return max([val_1, val_2, val_3])
优化代代码结构如下
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.res = None
    
    def maxPathSum(self, root: TreeNode) -> int:
        self.postOrder(root)
        return self.res
    
    def postOrder(self, root):
        if root is None:
            return 0
        l = max(0, self.postOrder(root.left))
        r = max(0, self.postOrder(root.right))
        if self.res is None:
            self.res = root.val

        sum = l + root.val + r
        self.res = max(sum, self.res)

        return max(l, r) + root.val