124. Binary Tree Maximum Path Sum 두 갈래 트리의 최대 경로 및
Title
비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다.
본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다.
예 1:
입력: [1,2,3]
1
/ \
2 3
출력: 6
예 2:
입력: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
출력: 42
Solve
차례로 돌아가다
먼저 간소화된 함수를 실현하는 것을 고려한다. 이 함수는 두 갈래 트리 중의 한 노드의 최대 공헌치를 계산한다. 구체적으로 말하면 이 노드를 뿌리 노드로 하는 하위 트리에서 이 노드를 기점으로 하는 경로를 찾아 이 경로의 노드 값을 최대로 하는 것이다.
구체적으로 이 함수의 계산 과정은 다음과 같다.
상술한 계산 과정은 귀속적인 과정이기 때문에 루트 노드에 이 함수를 호출하면 각 노드의 최대 공헌치를 얻을 수 있다.
각 노드의 최대 공헌치를 얻은 후, 두 갈래 트리의 한 노드에 대해 이 노드의 최대 경로와 이 노드의 값과 이 노드의 좌우 하위 노드의 최대 공헌치에 달려 있으며, 만약 하위 노드의 최대 공헌치가 정수라면 이 노드의 최대 경로와 그렇지 않으면 이 노드의 최대 경로와
전역 변수 maxSum을 유지하여 최대 경로를 저장하고 귀속 과정에서 maxSum의 값을 업데이트합니다. 마지막으로 얻은 maxSum의 값은 두 갈래 트리의 최대 경로와 같습니다.
Code
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.maxSum = float("-inf")
def maxPathSum(self, root: TreeNode) -> int:
def maxGain(node: TreeNode):
if not node:
return 0
leftGain = max(maxGain(node.left), 0)
rightGain = max(maxGain(node.right), 0)
priceNewPath = node.val + leftGain + rightGain
self.maxSum = max(self.maxSum, priceNewPath)
return node.val + max(leftGain, rightGain)
maxGain(root)
return self.maxSum
복잡도 분석
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
