2022/03/21 Mon 09:52    2022/11/16 Wed 23:42

leetcoad105-二叉树的最大路径和

题目描述：路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例一：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例二：

这个例子相对比较抽象，所以放了一张图上去
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
解题思路：
按照后序遍历的框架思路来解题：要求最大的路径和，对于一个二叉树结点，先计算左子树和右子树的最大路径和，然后加上自己的值，最后得出新的最大的路径和

看官方题解做的一点整理的东西：

路径和二叉树的数据结构有什么区别：

  1. 二叉树的特点：一个节点，被一个父节点连接，连接左右两个子节点
  2. 路径的特点：途径一个节点只能选择来去两个方向

思路：从根节点递归，每次递归分别走左边、右边、不动三种情况，用当前节点+左右子树的最大路径和不断的更新最大路径和（重复写了），注意不能同时走左边和右边

定义dfs（oneSideMax）函数，返回当前子树能向父节点提供的最大路径和（一条从父节点延申下来的路径，能在当前子树中捞取的的最大收益），分为三种情况：

  1. 路径停在当前子树的根节点，在当前子树的最大收益：root.val
  2. 走入左子树，在当前子树的最大收益：root.val+dfs(root.left)
  3. 走入右子树，在当前子树的最大收益：root.val+dfs(root.right)

最大的收益取三者的最大值：root.val+max(0,dfs(root.left),dfs(root.right))
子树中的内部路径要包含根节点：

  1. 最大路径和，是可能产生于其中一个子树中的
  2. 每递归一个子树，都求一下当前子树内部的最大路径和，从中比较出最大的
  3. 个子树内部的路径，要包含当前子树的根节点
  4. 综合分析：一个子树内部的最大路径和=左子树提供的最大路径和+根节点+右子树提供的最大路径和（dfs(root.left）+root.val+dfs(root.right))

代码如下：

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # 定义一个全局变量，用于记录全局的最大路径和
        # 先初始化最大的一个路径和
        self.ans=float('-inf')
        # 定义递归函数：递归函数要做的就是返回当前节点可以为父节点提供的最大的收益
        def oneSideMax(root):
            if not root:
                return 0
            # 采用的是后续遍历的框架
            # 递归计算左子树的最大路径和
            left=max(0,oneSideMax(root.left))
            # 递归计算右子树的最大路径和
            right=max(0,oneSideMax(root.right))

            # 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大路径
            # 在递归的过程中还要不断的更新节点的最大路径（left--root---right的路径与历史最大值的一个比较）
            self.ans=max(self.ans,left+right+root.val)

            # 返回结点的最大路径和（返回经过root的单边最大分支给当前root的父节点计算使用）
            # 从上往下看，每次只能选择左或右，每次递归返回的是以当前节点可以为父节点提供的收益
            return max(left,right)+root.val

        # 调用oneSideMax函数，从根节点开始递归
        oneSideMax(root)
        return self.ans

做题反思：通过这题，更要加深对递归的认识，之前认识的可能还真不够充分，题解也是需要自己写了之后才能真正的明白，而且要反复的去咀嚼里面的文字和思想，这真的是一项很重要的功底….看别人的题解的时候就会发现别人是多么的努力尽管别人已经很优秀了。

联系其中的一题：

leetcoad543-二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
代码略

leetcoad99-恢复二叉搜索树

ToTOP
2018 bear