Daily LeetCode Challenge - 958. Check Completeness of a Binary Tree

Problem From.

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

오늘 문제는 트리가 주어졌을때, 그 tree 가 마지막 노드까지 가는데에 중간에 null 이 있는지 없는지 검사하는 문제였다.

이 문제는 BFS 로 풀 수 있었는데, empty 라는 플래그를 하나 두고, 탐색을 해나가다가 null 인 노드를 만나면 true 로 바꿔준다. 만약 null 노드가 마지막에 있다면 false 를 반환하지 않고, null 노드가 중간에 있다면 false 를 반환하는 식으로 문제를 풀 수 있었다.

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isCompleteTree(root: TreeNode?): Boolean {
        if( root == null) return true

        val queue = LinkedList<TreeNode?>()
        queue.add(root)
        var empty = false

        while(queue.isNotEmpty()){
            val node = queue.poll()

            if(node == null){
                empty = true
            }else{
                if(empty) return false
                queue.add(node.left)
                queue.add(node.right)
            }
        }
        return true
    }
}