958. Check Completeness of a Binary Tree

LeetCode medium original: C# #csharp #leetcode #medium #queue #tree #two-pointers

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

LeetCode Static

Дан корень бинарного дерева, определите, является ли оно полным бинарным alberoм.

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

Esempio:

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

Output: true

Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

C# soluzione

abbinato/originale

public class Solution {
    public bool IsCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);
        bool nullNodeFound = false;
        while (q.Count > 0) {
            TreeNode node = q.Dequeue();
            if (node == null) {
                nullNodeFound = true;
            } else {
                if (nullNodeFound) {
                    return false;
                }
                q.Enqueue(node.left);
                q.Enqueue(node.right);
            }
        }
        return true;
    }
}

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 bool IsCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        queue<TreeNode> q = new queue<TreeNode>();
        q.Enqueue(root);
        bool nullNodeFound = false;
        while (q.size() > 0) {
            TreeNode node = q.Dequeue();
            if (node == null) {
                nullNodeFound = true;
            } else {
                if (nullNodeFound) {
                    return false;
                }
                q.Enqueue(node.left);
                q.Enqueue(node.right);
            }
        }
        return true;
    }
}

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 boolean IsCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.Enqueue(root);
        boolean nullNodeFound = false;
        while (q.size() > 0) {
            TreeNode node = q.poll();
            if (node == null) {
                nullNodeFound = true;
            } else {
                if (nullNodeFound) {
                    return false;
                }
                q.Enqueue(node.left);
                q.Enqueue(node.right);
            }
        }
        return true;
    }
}

JavaScript soluzione

abbinato/originale

var isCompleteTree = function(root) {
    if (root === null) {
        return true;
    }

    let queue = [root];
    let nullNodeFound = false;

    while (queue.length > 0) {
        let node = queue.shift();
        
        if (node === null) {
            nullNodeFound = true;
        } else {
            if (nullNodeFound) {
                return false;
            }
            queue.push(node.left);
            queue.push(node.right);
        }
    }
    return true;
};

Python soluzione

abbinato/originale

from collections import deque

class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        if not root:
            return True

        queue = deque([root])
        nullNodeFound = False

        while queue:
            node = queue.popleft()
            
            if not node:
                nullNodeFound = True
            else:
                if nullNodeFound:
                    return False
                queue.append(node.left)
                queue.append(node.right)

        return True

Go soluzione

abbinato/originale

func isCompleteTree(root *TreeNode) bool {
    if root == nil {
        return true
    }

    queue := []*TreeNode{root}
    nullNodeFound := false

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        if node == nil {
            nullNodeFound = true
        } else {
            if nullNodeFound {
                return false
            }
            queue = append(queue, node.Left)
            queue = append(queue, node.Right)
        }
    }
    return true
}

Algorithm

Если корень дерева равен null, return true.

Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.

Пока очередь не пуста:

Извлеките первый element из очереди.

Если element равен null, установите nullNodeFound в true.

Если element не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, return false. В противном случае добавьте в очередь левого и правого потомков текущего узла.

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte

Non ci sono ancora offerte attive.