LeetCode 124. ツリー内の最大パスとPython
空でないツリーを指定し、最大パスとを返します.
本題では,経路はツリー内の任意のノードから任意のノードに達するシーケンスとして定義される.パスには少なくとも1つのノードが含まれており、ルートノードを通過する必要はありません.
例1:
例2:
考え方:
再帰的には、各ノードがルートノードとして再帰関数に渡されます.現在のノードについて、ルートノードとして、左サブツリーパスの最大和、右サブツリーパスの最大和を計算します.このノードを介して、現在はそのルートノードと見なされています.このノードの最大パスとは、左サブツリーの最大パスと(0より大きい場合)+右サブツリーの最大パスと(0より大きい場合)+ルートノードの値です.そして、現在計算されているMAXがいくらなのか、つまり私たちの結果を更新します.
再帰関数の戻り値は、現在のノードの左サブツリー最大パスと、右サブツリー最大パスとです.ノード値を加算します.このようにして得られる最大パスは、このノードの親ノードの計算に使用できるパスとして使用されるからである.
コード:
本題では,経路はツリー内の任意のノードから任意のノードに達するシーケンスとして定義される.パスには少なくとも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))