leetcode-124-2차 트리의 최대 경로와

3663 단어

제목


제목 링크: 124-두 갈래 트리의 최대 경로 및
비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다.
본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다.
예제 1
 : [1,2,3]

       1
      / \
     2   3

 : 6

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

   -10
   / \
  9  20
    /  \
   15   7

 : 42

코드


python

class Solution:
    res = float('-inf')
    def maxPathSum(self, root: TreeNode) -> int:
        self.getMax(root)
        return self.res
    
    def getMax(self,root):
        if not root:
            return 0
        #  0 
        left = max(0, self.getMax(root.left))
        right = max(0, self.getMax(root.right))
        #  , 
        self.res = max(self.res, root.val + left + right)
        #  【 】 
        return max(left, right) + root.val

좋은 웹페이지 즐겨찾기