개인적으로 복습하다가 트리 부분을 찾아보고 있는 와중에
이진 트리의 root가 주어졌을때, 이 트리가 완전한지 체크하는 알고리즘에 대해 생각해보라는 문제를 보고 고민해보면서 구글링하면서 공부한 내용을 정리하려고 한다.
먼저 완전 이진 트리란 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있으며 마지막 레벨의 node들은 가능한 한 왼쪽부터 채워져 있는 구조를 말한다.
(A)의 경우는 완전 이진 트리이고, (B)의 경우 아니다.
기본적으로 tree의 level을 기준으로 왼쪽에서 오른쪽 순으로 탐색을 진행한다.
그 전에 full node라는 용어를 정의하는데, 이는 left, right child node가 모두 존재하는 노드를 칭한다.
완전 이진 트리라면 2가지 조건을 만족해야 하는데,
- tree 탐색 중에 full node가 아닌 node를 만날 경우, 그 node는 반드시 두 child node가 없거나 left node만 존재해야 한다.
2. 그리고 그 이후에 탐색하게 되는 node들은 모두 leaf node여야 한다.
이런 논리대로 구현해본 코드는 다음과 같다.
먼저 level 순으로 탐색하기 위해 bfs로 탐색하는데, queue에는 left child부터 enqueue해서 왼쪽부터 오른쪽으로 탐색하는 방식으로 구현했다.
non-full node를 만났을때 bfs를 중단하고 queue에 남아있는 node가 모두 leaf node인지 체크한다.
아래 링크는 공부하면서 참고한 페이지이다.
