222

leetcode easy

#csharp#easy#leetcode#math#search#tree#two-pointers

Task

. Count Complete Tree Nodes

Учитывая корень полного двоичного дерева, верните количество узлов в дереве.

Согласно Википедии, в полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. Он может содержать от 1 до 2 в степени n узлов включительно на последнем уровне n.

C# solution

matched/original

public class Solution {
    public int computeDepth(TreeNode node) {
        int d = 0;
        while (node.left != null) {
            node = node.left;
            ++d;
        }
        return d;
    }
    public bool exists(int idx, int d, TreeNode node) {
        int left = 0, right = (int)Math.Pow(2, d) - 1;
        for (int i = 0; i < d; ++i) {
            int pivot = left + (right - left) / 2;
            if (idx <= pivot) {
                node = node.left;
                right = pivot;
            } else {
                node = node.right;
                left = pivot + 1;
            }
        }
        return node != null;
    }
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int d = computeDepth(root);
        if (d == 0) return 1;
        int left = 1, right = (int)Math.Pow(2, d) - 1;
        while (left <= right) {
            int pivot = left + (right - left) / 2;
            if (exists(pivot, d, root)) left = pivot + 1;
            else right = pivot - 1;
        }
        return (int)Math.Pow(2, d) - 1 + left;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int computeDepth(TreeNode node) {
        int d = 0;
        while (node.left != null) {
            node = node.left;
            ++d;
        }
        return d;
    }
    public bool exists(int idx, int d, TreeNode node) {
        int left = 0, right = (int)Math.Pow(2, d) - 1;
        for (int i = 0; i < d; ++i) {
            int pivot = left + (right - left) / 2;
            if (idx <= pivot) {
                node = node.left;
                right = pivot;
            } else {
                node = node.right;
                left = pivot + 1;
            }
        }
        return node != null;
    }
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int d = computeDepth(root);
        if (d == 0) return 1;
        int left = 1, right = (int)Math.Pow(2, d) - 1;
        while (left <= right) {
            int pivot = left + (right - left) / 2;
            if (exists(pivot, d, root)) left = pivot + 1;
            else right = pivot - 1;
        }
        return (int)Math.Pow(2, d) - 1 + left;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int computeDepth(TreeNode node) {
        int d = 0;
        while (node.left != null) {
            node = node.left;
            ++d;
        }
        return d;
    }
    public boolean exists(int idx, int d, TreeNode node) {
        int left = 0, right = (int)Math.pow(2, d) - 1;
        for (int i = 0; i < d; ++i) {
            int pivot = left + (right - left) / 2;
            if (idx <= pivot) {
                node = node.left;
                right = pivot;
            } else {
                node = node.right;
                left = pivot + 1;
            }
        }
        return node != null;
    }
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int d = computeDepth(root);
        if (d == 0) return 1;
        int left = 1, right = (int)Math.pow(2, d) - 1;
        while (left <= right) {
            int pivot = left + (right - left) / 2;
            if (exists(pivot, d, root)) left = pivot + 1;
            else right = pivot - 1;
        }
        return (int)Math.pow(2, d) - 1 + left;
    }
}

Explanation

Algorithm

Пример:

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

Output: 6

👨‍💻

Алгоритм:

Инициализация и проверка пустоты дерева

Если дерево пустое, вернуть 0.

Рассчитать глубину дерева d.

Поиск узлов на последнем уровне

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

Вычисление общего количества узлов

Вернуть сумму узлов на всех уровнях, кроме последнего, и узлов на последнем уровне.

😎