LeetCode 124. ツリー内の最大パスとPython


空でないツリーを指定し、最大パスとを返します.
本題では,経路はツリー内の任意のノードから任意のノードに達するシーケンスとして定義される.パスには少なくとも1つのノードが含まれており、ルートノードを通過する必要はありません.
例1:
  : [1,2,3]

       1
      / \
     2   3

  : 6

例2:
  : [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

  : 42

考え方:
再帰的には、各ノードがルートノードとして再帰関数に渡されます.現在のノードについて、ルートノードとして、左サブツリーパスの最大和、右サブツリーパスの最大和を計算します.このノードを介して、現在はそのルートノードと見なされています.このノードの最大パスとは、左サブツリーの最大パスと(0より大きい場合)+右サブツリーの最大パスと(0より大きい場合)+ルートノードの値です.そして、現在計算されているMAXがいくらなのか、つまり私たちの結果を更新します.
再帰関数の戻り値は、現在のノードの左サブツリー最大パスと、右サブツリー最大パスとです.ノード値を加算します.このようにして得られる最大パスは、このノードの親ノードの計算に使用できるパスとして使用されるからである.
コード:
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#       :  2   ,        
#   1       2.             pathsum,         3.              ,f(root) = f(left)  .... f(right)
#                ,         
#         ,                       
class Solution:
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.re = -2**31
        
        self.robot(root)
        return self.re
    
    def robot(self,root):
        if root == None:
            return 0
        left = max(0,self.robot(root.left))
        right = max(0,self.robot(root.right))
        self.re = max(self.re,root.val + left + right)
        return max(root.val,root.val + max(left,right))