222

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

Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.

LeetCode Static

. Count Complete Tree Nodes

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

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

C# Lösung

zugeordnet/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++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen

#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 Lösung

Auto-Entwurf, vor dem Einreichen prüfen

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

Beispiel:

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

Output: 6

👨‍💻

Algorithmus:

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

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

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

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

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

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

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

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.