forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEgonD3V.py
More file actions
67 lines (49 loc) · 1.69 KB
/
EgonD3V.py
File metadata and controls
67 lines (49 loc) · 1.69 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from typing import Optional
from unittest import TestCase, main
# 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:
return self.solve_dfs(root)
"""
Runtime: 11 ms (Beats 98.62%)
Time Complexity: O(n)
> dfs를 통해 모든 node를 방문하므로 O(n)
Memory: 22.10 MB (Beats 10.70%)
Space Complexity: O(n)
- dfs 재귀 호출 스택의 깊이는 이진트리가 최악으로 편향된 경우 O(n), upper bound
- 나머지 변수는 O(1)
> O(n), upper bound
"""
def solve_dfs(self, root: Optional[TreeNode]) -> int:
max_path_sum = float('-inf')
def dfs(node: Optional[TreeNode]) -> int:
nonlocal max_path_sum
if not node:
return 0
max_left = max(dfs(node.left), 0)
max_right = max(dfs(node.right), 0)
max_path_sum = max(max_path_sum, node.val + max_left + max_right)
return node.val + max(max_left, max_right)
dfs(root)
return max_path_sum
class _LeetCodeTestCases(TestCase):
def test_1(self):
root = TreeNode(-10)
node_1 = TreeNode(9)
node_2 = TreeNode(20)
node_3 = TreeNode(15)
node_4 = TreeNode(7)
node_2.left = node_3
node_2.right = node_4
root.left = node_1
root.right = node_2
# root = [-10, 9, 20, None, None, 15, 7]
output = 42
self.assertEqual(Solution().maxPathSum(root), output)
if __name__ == '__main__':
main()