Kotlin | LeetCode

Задача: 222. Count Complete Tree Nodes
Сложность: easy

Учитывая корень полного двоичного дерева, верните количество узлов в дереве. Согласно Википедии, в полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. Он может содержать от 1 до 2 в степени n узлов включительно на последнем уровне n. Разработайте алгоритм, который выполняется за время, меньшее, чем O(n).

Пример:

Input: root = [1,2,3,4,5,6]
Output: 6

👨‍💻

Алгоритм:

1⃣Инициализация и проверка пустоты дерева
Если дерево пустое, вернуть 0.
Рассчитать глубину дерева d.

2⃣Поиск узлов на последнем уровне
Использовать двоичный поиск, чтобы найти количество узлов на последнем уровне. Функция exists используется для проверки наличия узла по индексу.

3⃣Вычисление общего количества узлов
Вернуть сумму узлов на всех уровнях, кроме последнего, и узлов на последнем уровне.

😎

Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun computeDepth(node: TreeNode?): Int {
        var node = node
        var d = 0
        while (node?.left != null) {
            node = node.left
            d++
        }
        return d
    }

    fun exists(idx: Int, d: Int, node: TreeNode?): Boolean {
        var left = 0
        var right = Math.pow(2.0, d.toDouble()).toInt() - 1
        var node = node
        for (i in 0 until d) {
            val pivot = left + (right - left) / 2
            if (idx <= pivot) {
                node = node?.left
                right = pivot
            } else {
                node = node?.right
                left = pivot + 1
            }
        }
        return node != null
    }

    fun countNodes(root: TreeNode?): Int {
        if (root == null) return 0
        val d = computeDepth(root)
        if (d == 0) return 1

        var left = 1
        var right = Math.pow(2.0, d.toDouble()).toInt() - 1
        while (left <= right) {
            val pivot = left + (right - left) / 2
            if (exists(pivot, d, root)) left = pivot + 1
            else right = pivot - 1
        }

        return Math.pow(2.0, d.toDouble()).toInt() - 1 + left
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post