[Leetcode][958] Check Completeness of a Binary Tree

문제 : https://leetcode.com/problems/check-completeness-of-a-binary-tree/

---

위 그림에서 보면 완전이진트리라면 배열에 저장될 때 현재 노드 인덱스(n) 기준으로 왼쪽 자식 노드는 2n 인덱스에, 오른쪽 자식 노드는 2n+1 인덱스에 저장된다.

이를 이용하여 루트부터 자식노드들을 탐색하면서 노드가 저장되는 인덱스 중 최대 값을 구하고 총 노드 수를 구한다.

만약 완전이진트리라면 인덱스의 최대값과 노드 수는 같을 것이고 완전이진트리가 아니라면 인덱스의 최대값이 노드 수보다 클 것이다.

시간 복잡도는 노드 수를 N이라 할 때 O(N).

---

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