[LeetCode] 543. Diameter of Binary Tree

이 문제는 이진트리에서 가장 긴 경로를 구하는 것이다.

처음 문제를 접근할 때, 이진트리의 가장 긴 경로는 루트 노드에서 제일 하단의 왼쪽 자식 또는 제일 하단의 오른쪽 자식까지의 높이라고 생각했다.

그러나 제일 하단의 노드들 사이의 경로도 고려를 해야한다. 물론 이 두 노드 사이의 반드시 루트 노드가 지나갈 필요는 없다.

정리하자면,

1. 루트 노드 - 왼쪽을 리프 노드
2. 루트 노드 - 오른쪽 리프 노드
3. 리프 노드 - 또 다른 리프 노드

3번의 경우를 고려하지 못해서 문제를 풀지 못했다. 사실 고려했어도 어떻게 하면 풀 수 있는지 몰랐다.

1번과 2번은 깊이 우선 탐색으로 쉽게 구할 수 있다.

그러나 3번은 명확하게 보이지 않았는데, 왼쪽 노드와 오른쪽 노드의 길이를 구하고 합치는 과정을 중간에 끼워 넣으면 된다.

그리고 핵심은 전역 변수로 최댓값을 저장하면서 진행하는 것이다. 따로 매개 변수를 넣지 말고 전역 변수로 활용하면 더 쉽다.

Reference

- https://handhand.tistory.com/46