문제

• path는 node를 최대 한번씩만 거치는 edge의 연속
• root를 통할 필요는 없음
• path sum은 그 path의 node 값 들의 합
• max path sum
• non-empty path

풀이

• root부터 recursion으로 쭉 내려가
• 올라오면서 계산하는 left+root, right+root,left+rigt+root, root 가 현재 subTree의 최대 path sum
• left+right+root는 지금이 마지막이니까 나머지 중 max를 return해서 더 커질 수 있도록

# 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:
        global path
        path = set()
        recursion(root)
        return max(path)
        
        
def recursion(root):
    global path
    leftTree, rightTree = 0, 0
    
    if root.left:
        leftTree = recursion(root.left)
    if root.right:
        rightTree = recursion(root.right)
    
    pathSum = [root.val]
    pathSum.append(leftTree + root.val) # left+root
    pathSum.append(rightTree + root.val) # right+root
    pathSum.append(leftTree + rightTree + root.val) # left + right + root
    
    path.add(max(pathSum))
    return max(pathSum[:3])

결과

돌릴때마다 속도가 달라져..... 76.87% 속도 나올것같다

다른 풀이

# 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:
        global maxi
        maxi = -1001
        recursion(root)
        return maxi
        
        
def recursion(root):
    global maxi
    leftTree, rightTree = 0, 0
    
    if root.left:
        leftTree = recursion(root.left)
    if root.right:
        rightTree = recursion(root.right)
    
    pathSum = [root.val]
    pathSum.append(leftTree + root.val) # left+root
    pathSum.append(rightTree + root.val) # right+root
    pathSum.append(leftTree + rightTree + root.val) # left + right + root
    
    maxi = max(maxi, max(pathSum))
    return max(pathSum[:3])    

이건 set에 넣는대신, 그때 그때 max 연산을 돌려주었다

크게 차이나진 않는다