forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathyyyyyyyyyKim.py
More file actions
30 lines (23 loc) ยท 1.11 KB
/
yyyyyyyyyKim.py
File metadata and controls
30 lines (23 loc) ยท 1.11 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
# DFS + ๋ถํ ์ ๋ณตํ DP
# ์๊ฐ๋ณต์ก๋ O(n), ๊ณต๊ฐ๋ณต์ก๋ O(n)
self.answer = float('-inf') # ์ต์ ๊ฐ์ ์ด๊ธฐ๊ฐ์ผ๋ก ์ธํ
(dfsํจ์์์๋ ์ฐ์ผ ์ ์๊ฒ ์ธ์คํด์ค๋ณ์ ์ ์ธํด์ ์ ์ญ๋ณ์์ฒ๋ผ ์ฌ์ฉ)
def dfs(node):
if not node:
return 0
# ์ผ์ชฝ, ์ค๋ฅธ์ชฝ ์๋ธํธ๋ฆฌ์์ ์ต๋ํฉ(์์๋ผ๋ฉด ๋ฒ๋ฆฌ๊ณ 0 ๊ฐ์ ธ๊ฐ๊ธฐ)
left = max(0,dfs(node.left))
right = max(0,dfs(node.right))
# ํ์ฌ ๋
ธ๋๋ฅผ ํฌํจํ๋ ์ต๋ํฉ์ผ๋ก answer ์
๋ฐ์ดํธ
self.answer = max(self.answer, left + right + node.val)
# ์ผ์ชฝ,์ค๋ฅธ์ชฝ ์ค ์ต๋๊ฐ ์ ํ(ํ๋ฐฉํฅ์ด๋๊น)ํด์ ๋ถ๋ชจ์๊ฒ ๋ฆฌํด
return max(left, right) + node.val
dfs(root)
return self.answer