FilesExpand file tree

 main

/

doh6077.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

48 lines (45 loc) · 1.69 KB

 main

/

doh6077.py

Top

File metadata and controls

• Code
• Blame

48 lines (45 loc) · 1.69 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# 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

from collections import deque

class Solution:

def maxPathSum(self, root: Optional[TreeNode]) -> int:

# # Initially thought I need to use BFS ( misunderstood the question)

# if not root:

# return

# queue = deque([root])

# result = []

# val = 0

# max_sum = float('-inf')

# while queue:

# currentNode = queue.popleft()

# result.append(currentNode.val)

# val += currentNode.val

# if currentNode.left:

# queue.append(currentNode.left)

# val += currentNode.left.val

# if currentNode.right:

# queue.append(currentNode.right)

# val += currentNode.right.val

# max_sum = max(val, max_sum)

# val = 0

# return max_sum

res = [root.val]

def dfs(root):

if not root:

return 0

leftMax = dfs(root.left)

rightMax = dfs(root.right)

# 자식 값이 음수일경우 0으로 처리

leftMax = max(leftMax, 0)

rightMax = max(rightMax, 0)

# "지금까지 발견한 경로 중 최고의 합"을 res[0]에 저장

# Job 1: 나를 꺾임점(Anchor)으로 하는 '아치형' 경로 계산

res[0] = max(res[0], root.val + leftMax + rightMax)

# Job 2: 부모에게 올릴 '직선' 경로 리턴

return root.val + max(leftMax, rightMax)

dfs(root)

return res[0]