Tree: 124. Binary Tree Maximum Path Sum

LeetCode/주제별 보충

Tree: 124. Binary Tree Maximum Path Sum

hyunkookim 2024. 12. 14. 17:40

124. Binary Tree Maximum Path Sum

문제가 요구하는 것

Binary Tree Maximum Path Sum:
- 트리에서 경로의 최대 합을 구하는 문제입니다.
- "경로"는 트리의 어떤 노드에서 시작하여 하위 노드를 따라가거나, 중간에서 멈출 수 있으며, 반드시 루트를 거칠 필요는 없습니다.
- 경로의 합은 경로에 있는 노드 값들의 합으로 계산됩니다.
- "최대 합"은 가능한 경로들 중 가장 큰 합입니다.

Mutable(변경 가능) 객체 와 Immutable(변경 불가능) 객체

파이썬에서 mutable(변경 가능) 객체와 immutable(변경 불가능) 객체는 객체의 성질에 따라 구분됩니다. 아래는 각각의 주요 예시를 정리한 표입니다.

1. Mutable(변경 가능) 객체

특징:
- 객체를 생성한 후 내부 데이터를 변경할 수 있음.
- 새로운 객체를 생성하지 않고도 값을 수정 가능.
예시:

Mutable 객체설명

list	리스트: 값을 추가/삭제/변경 가능. my_list[0] = 42
dict	딕셔너리: 키-값 쌍을 추가/삭제/변경 가능. my_dict['key'] = 'new_value'
set	집합: 요소를 추가/삭제 가능. my_set.add(42)
bytearray	바이트 배열: 데이터를 바이트 단위로 변경 가능. my_bytearray[0] = 65
user-defined classes	사용자가 정의한 클래스의 객체에서 속성 값을 변경 가능 (속성을 mutable로 선언한 경우).

Mutable 객체 예시

# list
my_list = [1, 2, 3]
my_list[0] = 42  # 변경 가능
print(my_list)  # 출력: [42, 2, 3]

# dict
my_dict = {'a': 1, 'b': 2}
my_dict['a'] = 42  # 변경 가능
print(my_dict)  # 출력: {'a': 42, 'b': 2}

# set
my_set = {1, 2, 3}
my_set.add(4)  # 변경 가능
print(my_set)  # 출력: {1, 2, 3, 4}

2. Immutable(변경 불가능) 객체

특징:
- 객체를 생성한 후 내부 데이터를 변경할 수 없음.
- 데이터를 수정하려고 하면, 새로운 객체가 생성됨.
예시:

Immutable 객체설명

int	정수형: 값을 변경하려면 새로운 객체가 생성됨. a = 1; a = 2
float	부동소수점: 값을 변경하려면 새로운 객체가 생성됨. b = 1.1; b = 2.2
str	문자열: 값을 변경하려면 새로운 객체가 생성됨. s = 'hello'; s = 'world'
tuple	튜플: 값을 변경할 수 없음.
frozenset	고정된 집합: 요소를 추가/삭제할 수 없음.
bytes	바이트 시퀀스: 불변형 데이터.

Immutable 객체 예시

# int
a = 1
print(id(a))  # 객체 ID 출력
a += 1  # 새로운 객체 생성
print(id(a))  # 다른 객체 ID

# str
s = "hello"
print(id(s))  # 객체 ID 출력
s += " world"  # 새로운 객체 생성
print(id(s))  # 다른 객체 ID

# tuple
my_tuple = (1, 2, 3)
# my_tuple[0] = 42  # 오류 발생: TypeError: 'tuple' object does not support item assignment

Mutable vs Immutable의 차이

특성	Mutable 객체	Immutable 객체
데이터 수정 가능 여부	가능	불가능
새 객체 생성 여부	수정 시 새 객체 생성 없음	수정 시 새로운 객체 생성
예제	list, dict, set	int, float, str, tuple, frozenset

주의할 점

Mutable 객체를 함수에 전달하면 함수 내부에서 수정한 값이 원본에 영향을 미칩니다.
Immutable 객체를 함수에 전달하면 함수 내부에서 수정된 값은 원본에 영향을 주지 않습니다.

Mutable 예제

def modify_list(lst):
    lst.append(4)  # 원본 리스트가 변경됨

my_list = [1, 2, 3]
modify_list(my_list)
print(my_list)  # 출력: [1, 2, 3, 4]

Immutable 예제

def modify_int(x):
    x += 1  # 새로운 객체가 생성되며, 원본에 영향 없음

a = 1
modify_int(a)
print(a)  # 출력: 1

Immutable 객체 + nonlocal 사용 예제:

- 'nonlocal' 사용해서 전역 처럼 사용 가능

def counter():
    count = 0  # Immutable 객체 (int)

    def increment():
        nonlocal count  # 외부 함수의 count 변수를 수정 가능하도록 선언
        count += 1  # count 값을 수정
        return count

    return increment

# counter 함수를 호출해 increment 함수 반환
increment_func = counter()

# increment 함수 호출로 count 값을 증가
print(increment_func())  # 출력: 1
print(increment_func())  # 출력: 2
print(increment_func())  # 출력: 3

중요 포인트

왜 nonlocal이 필요한가?
- 기본적으로 내부 함수는 외부 함수의 변수를 수정할 수 없습니다.
- nonlocal을 사용하면 내부 함수가 외부 함수의 변수를 수정 가능하게 만듭니다.
nonlocal vs global
- nonlocal: 가장 가까운 외부 함수의 변수에 접근.
- global: 전역 변수에 접근.

global과의 차이

count = 0  # 전역 변수

def increment():
    global count  # 전역 변수 count를 사용
    count += 1
    return count

print(increment())  # 출력: 1
print(increment())  # 출력: 2

nonlocal은 지역 스코프에서 변수를 관리할 때, global은 전역 스코프에서 변수를 관리할 때 사용됩니다.

결론

Mutable 객체는 데이터 수정이 필요한 경우 유용하지만, 주의하지 않으면 원본 데이터가 의도치 않게 변경될 수 있습니다.
Immutable 객체는 안전하게 데이터를 유지할 수 있지만, 데이터를 수정하려면 새 객체를 생성해야 합니다.

필요에 따라 mutable과 immutable 객체를 적절히 활용하면 됩니다! 😊

최대 경로 합을 구하는 문제의 본질

경로 정의:
- 경로는 트리의 어느 노드에서 시작해서 하위 노드를 따라가며, 어느 노드에서든 끝날 수 있습니다.
- 루트를 반드시 포함할 필요는 없습니다.
- 경로는 **"연결된 노드의 집합"**을 의미하며, "분할"되는 경로도 고려해야 합니다.
경로 분할:
- "현재 노드에서의 경로 합"은 왼쪽 서브트리의 최대 경로 합 + 오른쪽 서브트리의 최대 경로 합 + 현재 노드 값입니다.
- 이 값은 "최대 경로 합"을 갱신할 때 사용됩니다.
- 하지만 상위 노드로 반환하는 값은 한쪽 경로만 포함해야 합니다.

왜 한쪽 경로만 반환하는가?

1. 트리 구조의 특성

트리의 부모-자식 관계에서는 "부모 노드 → 자식 노드"로만 이동합니다.
상위 노드로 값을 반환할 때는 **"연결된 경로"**를 유지해야 하므로, 현재 노드에서 왼쪽 또는 오른쪽 하위 경로 중 하나만 선택해야 합니다.
두 개의 하위 경로를 모두 포함하면 상위 노드에서 트리가 분리된 경로처럼 보이게 됩니다.

2. 분할 경로 vs. 연결 경로

분할 경로 (현재 노드 + 왼쪽 최대 경로 + 오른쪽 최대 경로):
- 이는 **"완전한 경로"**로서, 상위 노드와는 연결되지 않은 독립적인 경로를 의미합니다.
- 이 값을 사용해 res[0]을 갱신하지만, 상위 노드로 반환할 필요는 없습니다.
연결 경로 (현재 노드 + 한쪽 하위 경로):
- 상위 노드와 연결된 경로만 상위로 반환합니다.
- 따라서 root.val + max(leftMax, rightMax)를 반환합니다.

https://youtu.be/Hr5cWUld4vU?si=4Db1NiEYKr0Fygx2

# 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:
        # 전역 변수 res를 리스트로 선언하여 최대 경로 합을 저장
        res = [root.val]

        # DFS를 사용하여 트리의 최대 경로 합을 계산하는 헬퍼 함수
        def dfs(root):
            if not root:  # 현재 노드가 None이면 0을 반환
                return 0

            # 왼쪽 하위 트리의 최대 경로 합 계산
            leftMax = dfs(root.left)
            leftMax = max(0, leftMax)  # 음수 경로는 제외하고 0 또는 최대값 선택

            # 오른쪽 하위 트리의 최대 경로 합 계산
            rightMax = dfs(root.right)
            rightMax = max(0, rightMax)  # 음수 경로는 제외하고 0 또는 최대값 선택

            # 현재 노드에서의 최대 경로 합 계산 (분할 경로 포함)
            # 왼쪽 경로 + 현재 노드 값 + 오른쪽 경로의 합을 계산
            res[0] = max(res[0], root.val + leftMax + rightMax)

            # 상위 노드로 전달할 값 반환 (현재 노드 값 + 왼쪽/오른쪽 중 최대값)
            # 상위 노드는 하나의 경로만 연결할 수 있으므로 한쪽만 선택
            return root.val + max(leftMax, rightMax)

        # DFS 시작
        dfs(root)

        # 전역 변수 res에 저장된 최대 경로 합 반환
        return res[0]

        # 입력 트리 예시:
        #        1
        #       / \
        #      2   3
        #     / \
        #    4   5
        #
        # 동작 과정:
        # 1. 각 노드에서 왼쪽, 오른쪽 하위 트리의 최대 경로 합 계산
        # 2. 분할 경로의 최대 합을 계산하여 res[0]을 갱신
        # 3. 상위 노드로 전달할 경로 합은 한쪽만 선택 (left 또는 right)
        #
        # 최종 결과: 최대 경로 합은 4 -> 2 -> 1 -> 3 으로 11

nonlocal 사용해서..

# 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:
        # res = [root.val]
        res = root.val  # 초기 최대값을 root의 값으로 설정


        # return max path sum without split
        def dfs(root):  
            nonlocal res # res 를 전역 변수로..

            if not root:
                return 0

            leftMax = dfs(root.left)
            leftMax = max(0, leftMax)

            rightMax = dfs(root.right)
            rightMax = max(0, rightMax)
            
            # compute max path sum with split
            #res[0] = max(res[0], root.val+leftMax+rightMax)
            res = max(res, root.val+leftMax+rightMax)
        
            return root.val + max(leftMax, rightMax)
            
        dfs(root)
        #return res[0]
        return res

        # def dfs(node, currSum):
        #     if not node:
        #         return 0
            
        #     currSum += node.val

        #     return max(dfs(node.left, currSum), dfs(node.right, currSum), dfs(node.left, currSum)+dfs(node.right, currSum))

        # return dfs(root, 0)

대안 1: 전역 변수 없이 DFS로 구현

전역 변수를 사용하지 않고 반환값으로 최대 경로 합을 추적하는 방법입니다. 이 방법에서는 추가 변수를 사용하지 않고 함수 반환값을 통해 결과를 전달합니다.

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if not root:
                return (float('-inf'), 0)  # (최대 경로 합, 상위로 전달할 최대값)

            # 왼쪽과 오른쪽 하위 트리에서 최대값 계산
            leftMaxPath, leftSinglePath = dfs(root.left)
            rightMaxPath, rightSinglePath = dfs(root.right)

            # 현재 노드에서 가능한 최대 경로 합
            maxAtRoot = root.val + max(0, leftSinglePath) + max(0, rightSinglePath)

            # 현재까지의 최대 경로 합 계산
            maxPath = max(leftMaxPath, rightMaxPath, maxAtRoot)

            # 상위 노드로 전달할 값 (한쪽 경로만 선택)
            singlePath = root.val + max(0, leftSinglePath, rightSinglePath)

            return (maxPath, singlePath)

        # dfs 호출로 최대 경로 합 계산
        maxPath, _ = dfs(root)
        return maxPath

대안 2: BFS(너비 우선 탐색)로 트리의 경로 탐색

DFS가 아닌 BFS를 사용해 각 노드에서 최대 경로 합을 계산하는 방법입니다. 이 방식은 스택 대신 큐를 사용하며, 트리의 각 레벨을 순차적으로 탐색합니다.

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if not root:
                return (float('-inf'), 0)  # (최대 경로 합, 상위로 전달할 최대값)

            # 왼쪽과 오른쪽 하위 트리에서 최대값 계산
            leftMaxPath, leftSinglePath = dfs(root.left)
            rightMaxPath, rightSinglePath = dfs(root.right)

            # 현재 노드에서 가능한 최대 경로 합
            maxAtRoot = root.val + max(0, leftSinglePath) + max(0, rightSinglePath)

            # 현재까지의 최대 경로 합 계산
            maxPath = max(leftMaxPath, rightMaxPath, maxAtRoot)

            # 상위 노드로 전달할 값 (한쪽 경로만 선택)
            singlePath = root.val + max(0, leftSinglePath, rightSinglePath)

            return (maxPath, singlePath)

        # dfs 호출로 최대 경로 합 계산
        maxPath, _ = dfs(root)
        return maxPath

결론

전역 변수 없는 DFS: 함수 반환값을 통해 최대 경로 합을 추적할 수 있어 일반적으로 더 깔끔한 구현입니다.
BFS: 트리의 레벨별 탐색을 원하거나 재귀를 피하고 싶을 때 적합합니다.

# 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

        """
        maxSum = root.val 으로 선언해서 사용하고 싶으나, 일반 변수면.
        dfs() 함수 내에서 사용하려면, nonlocal 등의 파라미터를 사용해야되서
        다른 키워드 처리없이, 전역 변수로 사용하기위해, 리스트 변수로 만들어서 사용함
        """

        maxSum = [root.val] 

        def dfs(node):
            if not node:
                return 0

            leftMax = max(0, dfs(node.left))
            rightMax = max(0, dfs(node.right))

            maxSum[0] = max(maxSum[0], node.val + leftMax + rightMax)

            return node.val + max(leftMax, rightMax)

        dfs(root)
        return maxSum[0]

최종

# 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:        
        self.max_sum = -float("inf")
        
        def dfs_sum(node):
            if not node:
                return 0

            # 음수 노드로 인해 최대값이 왜곡되지 않고, 최대 경로 합이 정확히 계산하기 위해, 
            # max(0, ) 취함
            left_max = max(dfs_sum(node.left), 0) 
            right_max = max(dfs_sum(node.right), 0)
            self.max_sum = max(self.max_sum, 
                                left_max + right_max+ node.val)
            return max(left_max, right_max) + node.val
        
        dfs_sum(root)
        return self.max_sum

'LeetCode > 주제별 보충' 카테고리의 다른 글

Graphs: 130. Surrounded Regions★★ (0)	2024.12.16
DFS: Kth Smallest Element in a BST (1)	2024.12.15
DFS: 100. Same Tree (0)	2024.12.11
Graphs(Union Find): 547. Number of Provinces (0)	2024.11.18
Tree: 1448. Count Good Nodes in Binary Tree (2)	2024.11.15

현재글Tree: 124. Binary Tree Maximum Path Sum

hyunkookim 님의 블로그

hyunkookim 님의 블로그 입니다.

neetcode, BST, 누적합, leetcode75, 티스토리챌린지, Coding Test, dp, 우선순위큐, top150, 슬라이딩윈도우, array / string, Two pointers, LeetCode, 오블완, Backtracking, dfs, tree, BFS, heap, neetcode150,

Today :
Yesterday :

hyunkookim 님의 블로그