[Leetcode] 0124. 이진 트리 최대 경로 합

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

에이 길 이진 트리는 각 인접 노드 쌍이 그들을 연결하는 간선을 갖는 노드 시퀀스입니다. 노드는 시퀀스에만 나타날 수 있습니다. 최대 한 번. 경로가 루트를 통과할 필요는 없다는 점에 유의하세요.

그만큼 경로 합계 경로의 합은 경로에 있는 노드 값의 합입니다.

주어진 뿌리 이진 트리의 경우, 반환 최대 경로 합계 어떤 것의 비어 있지 않음 길.

예시 1:

입력: 루트 = [1,2,3]
산출: 6
설명: 최적의 경로는 2 -> 1 -> 3이고 경로 합은 2 + 1 + 3 = 6입니다.

예 2:

입력: 루트 = [-10,9,20,null,null,15,7]
산출: 42
설명: 최적 경로는 15 -> 20 -> 7이고 경로 합은 15 + 20 + 7 = 42입니다.

제약:

트리의 노드 수는 범위 내에 있습니다. [1, 3 * 10 ⁴ ].
-1000 <= 노드.val <= 1000

파이썬

				
					# 시간 복잡도: O(n) # 공간 복잡도: O(n) from typing import Optional class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class 해결책: def maxPathSum(self, root: Optional[TreeNode]) -> int: maxPath = float('-inf') def dfs(node: Optional[TreeNode]): nonlocal maxPath if node is None: return 0 pathLeft = max(dfs(node.left), 0) pathRight = max(dfs(node.right), 0) maxPath = max(maxPath, pathLeft + pathRight + node.val) return max(pathLeft + node.val, pathRight + node.val) dfs(root) return maxPath root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) print(Solution().maxPathSum(root))

파이썬

관련 기사