222

LeetCode easy original: C# #csharp #easy #leetcode #math #search #tree #two-pointers

Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.

LeetCode Static

. Count Complete Tree Nodes

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

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

C# soluzione

abbinato/originale

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++ soluzione

bozza automatica, rivedere prima dell'invio

#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 soluzione

bozza automatica, rivedere prima dell'invio

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;
    }
}

Algorithm

Esempio:

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

Output: 6

👨‍💻

Algoritmo:

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

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

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

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

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

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

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

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte

Non ci sono ancora offerte attive.