leetcode - CheckCompletenessofBinaryTree

주어진 이진트리가 완전 이진 트리인지 확인하는 문제이다.

알고리즘은 BFS 탐색을 이용해 풀었다.

BFS 탐색을 진행하면서, left나 right가 null이더라도 null Node를 탐색한것처럼 배열에 넣어 완전 이진트리인지 검사했다.

완전 이진트리이기 위해서는, BFS 탐색을 진행했을 때 null 노드를 방문했다면 앞으로 방문 할 노드들은 모두 null 노드이어야 한다.

예시

위의 예시는 완전 이진 트리가 아닌 경우인데, NULL 노드도 방문한다고 가정한 후(단말 노드의 자식 노드라면 방문하지 않는다.) BFS 탐색을 해보면, 1 -> 2 -> 3 -> 4 -> 5 -> NULL -> 7 과 같은 형태로 방문하게 된다.

이렇게 NULL 노드를 방문했다면 그 다음으로 방문 할 모든 노드들은 NULL이어야 완전 이진 트리의 조건을 만족하게 된다.

class Solution {
    static ArrayList<Integer> arr;
    public void bfs(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            arr.add(temp.val);
            if (temp.left != null) queue.add(temp.left);
            else if (temp.val != -1) queue.add(new TreeNode(-1, null, null));
            if (temp.right != null) queue.add(temp.right);
            else if (temp.val != -1) queue.add(new TreeNode(-1, null, null));
        }
    }
    public boolean isCompleteTree(TreeNode root) {
        arr = new ArrayList<>();
        bfs(root);
        boolean is_poss = true;
        for (int elem : arr) {
            if (elem == -1) {
                if (is_poss) {
                    is_poss = false;
                }
            }
            if (!is_poss && elem != -1) return false;
        }
        return true;
    }
}