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

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

通过次数62,276 | 提交次数145,587

First Try

2020-07-21

一开始的尝试是先进行处理，然后再对下游进行递归，考虑各种左边和右边为负数的情况，直接写乱了。看题解发现应该是先递归再处理的模式，对这种先假设一切已经搞定，然后再对搞定的结果进行处理的思维模式还是不太习惯。虽然这就是merge sort里面的典型思维方式。

不过知道先递归后处理的方式，还是对题目理解错误写了另外的failed try。一开始理解成整棵树的大小最大，这个还比较容易，后来发现是某条路径最大，这个就有点麻烦了。

还好进行尝试后通过了，毕竟递归到某个节点的时候，对于路径有两种需要考虑：其一是通过当前节点把左右子树连接起来；其二是把选择最大的子树加上当前节点，留待上一曾节点的递归。因此对于每个节点，都需要考虑两种情况的路径大小，但是返回用于递归的仅仅是最大子树的那个数值。

然后bingo，递归又把事情变得很简单。如果不用递归，这种问题都不知道要怎么个写法，太棘手了。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # [5,4,8,11,null,13,4,7,2,null,null,null,1]
        maxrv = {'rv':float('-inf')}
        def maxsum(root):
            if not root:
                return 0
            rv = root.val 
            left = maxsum(root.left)
            right = maxsum(root.right)
            large, small = (left, right) if left > right else (right, left)
            if small > 0: # 可以考虑在当下节点，把左边和右边都联系起来, 但是不返回到递归结果中
                maxrv['rv'] = max(maxrv['rv'], small + rv + large)
            if large > 0:
                rv += large  # 每次递归的时候，只考虑选择最大那条边进行递归
            maxrv['rv'] = max(maxrv['rv'], rv)
            return rv 

        maxsum(root)
        return maxrv['rv']

执行用时：68 ms, 在所有 Python 提交中击败了97.21%的用户
内存消耗：26 MB, 在所有 Python 提交中击败了50.00%的用户

failed try

以为是整棵树的和最大，其实应该是路径最大。

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        maxrv = {'rv':float('-inf')}
        def maxsum(root):
            if not root:
                return 0
            rv = root.val 
            left = maxsum(root.left)
            right = maxsum(root.right)
            if left > 0:
                rv += left
            if right > 0:
                rv += right
            maxrv['rv'] = max(maxrv['rv'], rv) 
            return rv  
        maxsum(root)
        return maxrv['rv']

failed try 2

错误的递归方式，考虑的是先处理完再递归，而且是从上层到下层进行递加的递归方式，写起来思路越来越乱。

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        maxs = {'rv': float('-inf')}
        def dfs(node, score):
            if not node:
                return 0
            val = node.val 
            if val + score < 0:
                dfs(node.left, 0)
                dfs(node.right, 0)
                maxs['rv'] = max(maxs['rv'], val)
                return 0 
            else:
                score += val 
                maxs['rv'] = max(maxs['rv'], score)
                maxrv = score + dfs(node.left, score) + dfs(node.right, score)
                maxs['rv'] = max(maxs['rv'], maxrv)
                return val 

        dfs(root, 0)
        return maxs['rv']

124. 二叉树中的最大路径和 [hard]​

First Try​

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

First Try