[Leetcode] 222. Count Complete Tree Nodes

문제 : https://leetcode.com/problems/count-complete-tree-nodes/

---

완전 이진 트리(complete binary tree)의 루트 노드가 입력으로 주어지면 트리의 노드 수를 반환해라.

시간복잡도를 O(N) 보다 작게 만들어라.

---

포화 이진 트리의 노드 수는 2^(트리 높이) - 1 임을 사용하자.

최좌측 단노드까지의 높이와 최우측 단노드까지의 높이가 같은 경우 포화 이진 트리가 된다.

높이가 다른 경우, 왼쪽 하위 노드들 수와  오른쪽 하위 노드들 수를 구해서 더하고 루트 노드 수인 1을 더한 값이 노드 수가 된다. 

왼쪽 하위 노드들 수와 오른쪽 하위 노드들 수는 재귀함수를 이용해 구한다.

 

완전이진트리인지 구하기 위해 log2N이 소요되고, 최악의 경우 높이를 탐색하기 위한 노드가 단노드가 될 수 있으므로 반복문은 log2N번 실행될 수 있다. 따라서 시간복잡도는 O(log2N * log2N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/222.%20Count%20Complete%20Tree%20Nodes.cpp