[LeetCode] 124. Binary Tree Maximum Path Sum (C++)

문제

 

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

Binary Tree Maximum Path Sum - LeetCode

 

 

풀이

 

난이도: Hard  

 

 

대표적인 DFS 심화 문제.

 

트리에서 Path 특정 노드에서 선을 그어 다른 노드까지 이어지는 경로와 같다.

단, 중복되는 노드를 지나쳐서는 안된다.

 

 

다음과 같은 서브 트리에서 가능한 최대 path sum을 계산해 보자.

 

이진트리에서 path sum이 계산될 경우의 수는 다음과 같다.

 

case 1: 왼쪽 서브 트리에서의 최대 path sum

case 2: 오른쪽 서브 트리에서의 최대 path sum

case 3: root의 값 + case1 + case 2의 값

case 4: root의 값 + case1 또는 root의 값 + case2의 값

case 5: root의 값

 

case 1과 2는 root의 양쪽 서브 트리 중에서 최대 path sum이 나와서 더 이상 path를 추가할 필요가 없는 경우이다.

노드의 값은 음수의 가능성이 있기 때문에, root 노드를 path 추가하는 것이 이득이 아니기 때문이다.

 

하지만 root 노드가 음수라도, 왼쪽과 오른쪽을 이어 준다면, 더 큰 path sum이 나올 수 있다.

예를 들어 양쪽이 4와 6의 결과가 나왔고, root의 값이 -1이라면 root를 추가해 4 + 6 - 1 = 9로 더 큰 path sum을 만들 수 있다. 이러한 경우가 case 3이다.

 

단, case 3는  root를 통해 양쪽을 이어주었으므로 상위 노드에서는 이 값을 사용할 수 없다. (상위와 경로를 이어주면 root노드를 중복으로 지나치게 된다.)

하위 트리에서 계산한 case 3가 여전히 정답인지는 알 수 없으므로 계속 path를 상위로 이어보아야 한다.

 

상위로 연결하기 위해서는 root를 지나고, 왼쪽 오른쪽 중 단 하나의 경로만 포함해야 한다.

 

이때는 두 가지 경우 중에 더 큰 값을 반환한다.

왼쪽과 오른쪽 중 더 큰 값과 root의 값(경로)을 합쳐 상위로 반환하거나 ->  case 4

root의 값만(root에서부터 새로운 경로)을 반환한다. -> case 5

 

 

이렇게 리프 노드부터 순차적으로 위로 계산해 올라는 알고리즘은 DFS이므로,

DFS를 위한 재귀적인 코드를 구현하면 아래와 같다.

 

 

 

코드