완전 이진 트리는 포화 이진 트리에서 오른쪽 리프(잎새)부터 제거해나간 형태의 트리이다. 포화 이진 트리는 잎새를 제외한 모든 노드에게 2개의 자식이 있는 이진 트리를 말한다.
위 설명에서 추론할 수 있는 점은 ↓
완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 빠짐없이 채워져 있어야 하며, 만약 마지막 레벨이 꽉 채워져 있지 않다면 왼쪽부터 채워져 있어야 한다.
포화 이진 트리 또한 완전 이진 트리이다.
이 점에 착안하여 문제를 풀 수가 있다.
- 포화 이진 트리인 경우: level 이 n 이라면
2의 n승 - 1이 총 노드의 개수이다. - 포화 이진 트리가 아닌 경우: 포화 이진 트리가 되는 것을 기저 조건으로 두고 recursion을 돌린다. 루트 노드 한 개 + 왼쪽 서브 트리의 총 노드 카운트 + 오른쪽 서브 트리의 총 노드 카운트
- 잎새: 자식이 없는 노드.
- 트리에 대한 설명은 포스트에 조금.