[Leetcode][124] Binary Tree Maximum Path Sum

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

---

서브트리의 루트 노드를 기준으로 만들 수 있는 sequence들은 다음과 같다.

1. 현재 루트노드, 루트노드의 왼쪽, 오른쪽 노드를 sequence로 가지는 경우.

2. 왼쪽 노드와 부모노드를 sequence로 가지는 경우

왼쪽 자식노드 value가 오른쪽 자식노드보다 크고 root와의 합이 0이거나 양수인 경우이다.

3. 오른쪽 노드와 부모 노드를 sequence로 가지는 경우

오른쪽 자식 노드가 왼쪽 자식노드보다 크고 오른쪽 자식 노드와 root노드의 value를 합한 값이 양수인 경우이다.

4. root노드만을 sequence에 포함시키는 경우

이 경우는 왼쪽 자식 노드와 오른쪽 자식 노드들이 모두 음수인 경우이다.

또한 root 노드의 value는 0이거나 양수여야 한다.

5. root노드의 서브트리를 포함하지 않고 sequence를 만드는 경우

이 경우는 root노드의 서브트리의 최적 sequence 합이 음수인 경우이다.

음수인 경우는 더하면 값이 작아지므로 버리는 것이 더 이득이다.

sequence는 위와 같이 총 5가지를 만들 수 있고, 이를 재귀함수로 만들어서 정답을 구할 수 있다.

재귀함수는 root 노드를 입력으로 받고 root 노드를 받았을 때 2, 3, 4, 5로 sequence를 구성했을 때 만들 수 있는 최대 합을 반환한다.

1번의 경우는 재귀함수 내에서 구하고 ans와 비교해서 큰 경우 ans를 갱신하면 된다.

재귀함수에서 반환되는 값은 root노드의 부모노드가 받아서 다른 sequence를 만들어 탐색하는데 사용된다.

1번 = 루트노드 + 재귀함수(left 노드) + 재귀함수(right 노드)

2번 = 루트노드 + 재귀함수(left 노드)

3번 = 루트노드 + 재귀함수(right 노드)

4번 = 루트노드

5번 = 0

위와 같이 값을 구할 수 있고 1번은 앞에서 말했다시피 재귀함수 내에서 ans 갱신용으로만 사용되고 반환하는 값을 만드는데 관여하지는 않는다.

(1번과 같은 모양의 sequence를 만드는 경우 부모노드가 sequence에 포함될 수 없기 때문)

2, 3, 4, 5 중 최대 값을 구해서 ans 갱신하는데 한 번 사용한 뒤(부모 노드를 포함하지 않았을 때 최적일 수 있기 때문) 반환해준다.

만약 모든 노드가 음수인 경우 트리에서 최대 노드값이 정답이 된다.

---

소스코드 : https://gist.github.com/fpdjsns/e72d37665a51768f00647d46f414ef0c