[Leetcode 아주 상세한 문제풀이] 124.Binary Tree Maximum Path Sum - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 124번 문제 Binary Tree Maximum Path Sum 이다.

우선 문제를 살펴보자.

 

리트코드 124번 문제 Binary Tree Maximum Path Sum 링크

https://leetcode.com/problems/binary-tree-maximum-path-sum/

LeetCode - The World's Leading Online Programming Learning Platform

 

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:
Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
 
Constraints:
The number of nodes in the tree is in the range [1, 3 * 104].
-1000 <= Node.val <= 1000

 

 

문제 설명

문제를 살펴보자. 우선 binary tree가 주어진다. Binary tree에 대해 간략히 설명하면 만약 [1, 2, 3]이란 배열이 주어졌을 때 첫번째 값 1은 가장 상단 node에, 그리고 2는 그 아래 왼쪽 node, 3은 그 아래 오른쪽 node에 위치하게 된다. 문제 예시 1번에서 보는 것처럼 (리트코드 공식 홈페이지 그림을 확인 바란다) 2층 짜리 binary tree가 만들어진다. 즉, 주어진 배열에서 하나씩 아래 층으로 내려가며 배열시키는데, 한 층 내려갈때 마다 좌/우에 하나씩 위치하게 된다.

이때 문제는 주어진 binary tree에서 각 노드를 한 번씩만 거쳐갈 때 얻을 수 있는 최대 합은 얼마인지 찾는 문제다. 노드를 한 번씩만 거쳐가면 되므로 문제 예시 2번에서 보는 것처럼 binary tree 윗 층으로 이동해도 상관 없다. 쉽게 말하면 주어진 binary tree에서 노드들을 따라 한붓 그리기를 했을 때 얻을 수 있는 최대 값은 얼마인지 찾는 문제다. 설명은 조금 어렵지만 문제에서 요구하는 것을 이해하는 것은 크게 어렵지 않으니 곧바로 문제를 풀어보자.

 

 

문제 접근법

이 문제에 대한 접근은 binary tree에 대한 이해에서 부터 시작하는 것이 좋다.

문제 예시 1번에서 보는 것처럼 아래와 같은 binary tree가 주어졌다고 생각해 보자.

해답에서 설명한대로 이 문제의 정답은 6이다 (=2+1+3).

즉, 2에서 시작해 1을 거쳐 3까지 끊어지지 않고 노드를 연결하면 위와 같은 답을 얻을 수 있다.

 

그렇다면 좀 더 복잡한 경우는 어떨까?

예를 들어 아래 도식처럼 오른쪽 노드 (3) 아래 4와 5라는 새로운 노드가 만들어졌다고 생각해 보자.

이 경우 우리는 파란색으로 표시된 부분, 즉 3을 상위 노드로 갖는 부분의 최대합을 계산해주면 된다.

만약 파란색 부분의 최대합을 구했다면 결국 위 예시 [1,2,3] 문제로 돌아가기 때문이다.

따라서 이 문제는 binary tree 아래쪽에 위치한 sub problem를 먼저 풀어가며

최종적으로 binary tree 전체에서 최대 합을 구하는 것이 문제의 핵심이다.

 

이 문제는 도식을 가지고 설명하는 것보다 곧바로 코드를 보는게 이해가 더 쉽다.

코드를 바로 살펴보자.

 

 

문제 풀이

우선 binary tree를 만들기 위한 class를 정의한다 (line 2-6)

이 코드에서 보여지는 것처럼 binary tree를 만들기 위한 일반적인 class 설정이니 익숙해 지도록 하자.

다음으로 문제를 풀 Solution class를 정의한다 (line 8)

여기에 이 문제에서 구하고자 하는 노드들의 최대합을 구하는 함수를 정의해 준다 (line 9)

이때 정의한 함수 안해 새로운 helper 함수를 또 정의해 주는데, (line 11)

이 함수가 바로 위에서 설명한 sub node (파란색 부분)의 최대값을 구하는 부분이다.

이 함수에 대해 살펴보면 우선 max_sum은 local 변수가 아님을 선언한다 (line 12)

우리는 max_sum을 helper 함수 안과 밖에서 모두 써야 하기 때문이다 (i.e. global 변수)

이 max_sum은 무한대 값 (음수) 으로 초기화를 시켜준다. (line 26)

그리고 만약 노드가 비어있다면 0을 리턴한다 (line 13-14)

이제 sub node (파란색 부분)에 대한 계산을 먼저 할 텐데,

그 sub node에서 왼쪽 노드와 오른쪽 노드의 최대합을 helper 함수를 재귀함으로써 구한다. (line 17-18)

Binary tree가 깊더라도 helper 함수를 재귀적으로 호출함으로써,

그 노드 아래에 있는 최대합을 구할 수 있다.

각 노드의 최대합을 구했다면 그때까지의 최대합을 구한다.

위 문제 접근에서 제시한 예에서 파란색 부분의 최대합을 구해본다.

그 이유는 파란색 부분의 합이 최대합이 될 수도 있고,

혹은 파란색 부분에서 왼쪽 혹은 오른쪽 노드만 취한 뒤

그 상위 노드 (1과 2)에서의 합이 최대합이 될 수도 있기 때문이다.

우리는 어떤값이 더 클지 모르는 상황이기 때문에 우선 max_sum을 업데이트 해준다.

마지막에 가장 상위 노드 (위의 예시에서 1, 2, 3)의 최대합을 구해주기 위해

helper 함수를 빠져나오며 그 노드의 값과 왼쪽 노드 혹은 오른쪽 노드 중 더 큰 값을 더해 리턴한다. (line 24)

그리고 최종적으로 max_sum을 리턴해주며 함수를 종료한다 (line 28)

 

 

문제 풀이 코드

# 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):
        # Helper function to find the maximum path sum starting from a node
        def maxPathSumFromNode(node):
            nonlocal max_sum
            if not node:
                return 0
 
            # Calculate the maximum path sum starting from the left and right subtrees
            left_sum = max(maxPathSumFromNode(node.left), 0)
            right_sum = max(maxPathSumFromNode(node.right), 0)
 
            # Update the maximum path sum found so far
            max_sum = max(max_sum, node.val + left_sum + right_sum)
 
            # Return the maximum path sum starting from this node
            return node.val + max(left_sum, right_sum)
 
        max_sum = float('-inf')  # Initialize max_sum to negative infinity
        maxPathSumFromNode(root)
        return max_sum
 
# Example usage:
# Construct the binary tree for the first example: [1,2,3]
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
 
# Create an instance of the Solution class
solution = Solution()
 
# Calculate and print the maximum path sum
print(solution.maxPathSum(root1))  # Output: 6
 

 

 

관련 문제

리트코드 98번 Validate binary search tree 문제 풀이 (링크)

리트코드 102번 Binary tree level order traversal 문제 풀이 (링크)

리트코드 104번 Maximum depth of binary tree 문제 풀이 (링크)

리트코드 105번 Construct binary tree from preoder and inorder traversal 문제 풀이 (링크)

리트코드 208번 Implement tree (Prefix tree) 문제 풀이 (링크)

리트코드 212번 Word search 2 문제 풀이 (링크)

리트코드 226번 Invert/flip binary tree 문제 풀이 (링크)

리트코드 235번 Lowest common ancestor of BST 문제 풀이 (링크)

리트코드 572번 Subtree of another tree 문제 풀이 (링크)

 

124.Binary Tree Maximum Path Sum