Ստուգեք ՝ տրված Երկուական ծառը ամբողջական է, թե ոչ


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Ցնծություն Ամերիքան Էքսպրես քարտ Տվյալների շտեմարաններ Օքսիգենային դրամապանակ Spotify
Երկուական ծառ Հերթ ծառ

Խնդիրի հայտարարություն

«Ստուգեք տրված Երկուական ծառը ամբողջական է, թե ոչ» խնդիրը ասում է, որ ձեզ տրված է երկուական ծառի արմատը, ստուգեք ՝ ծառը ամբողջական է, թե ոչ: Ամբողջական Երկուական ծառը լրացնում է իր բոլոր մակարդակները, բացառությամբ վերջին մակարդակի, իսկ վերջին մակարդակի հանգույցները մնում են որքան հնարավոր է:

Օրինակներ

Մուտքային

Ստուգեք ՝ տրված Երկուական ծառը ամբողջական է, թե ոչ

true

Մուտքային

Ստուգեք ՝ տրված Երկուական ծառը ամբողջական է, թե ոչ

false

Մոտեցում

A ամբողջական Երկուական ծառ է երկուական ծառ որում լրացված են բոլոր մակարդակները, բացառությամբ վերջին մակարդակի, և վերջին մակարդակի հանգույցները մնում են որքան հնարավոր է:

Ստուգելու համար, որ երկուական ծառը ամբողջական է, թե ոչ, մենք կարող ենք օգտագործել այն մակարդակի կարգի անցում ծառի

  1. Սահմանեք ամբողջական հանգույցը որպես հանգույց, որն ունի թե՛ ձախ, թե՛ աջ երեխա ՝ որպես ոչ առնական:
  2. Լրիվ ծառի համար, եթե մակարդակի կարգի անցման ժամանակ մենք տեսնում ենք ոչ ամբողջական հանգույց, ապա այս հանգույցից հետո բոլոր հանգույցները պետք է լինեն տերևային հանգույցներ, այլապես ծառը ամբողջական չէ:
  3. Նաև եթե աջ երեխայի հետ հանգույց կա, քանի որ այն զրոյական է, իսկ ձախը ՝ որպես զրոյական, ծառը ամբողջական չէ:

Ալգորիթմ

  1. Եթե ​​արմատը զրոյական է, վերադարձիր ճշմարիտ:
  2. Ստեղծեք հերթ և արմատային հանգույցը սեղմեք դրան: Նախ հայտնաբերեք հայտնաբերված բոնյան փոփոխականը որպես սխալ:
  3. Չնայած հերթը դատարկ չէ, կրկնում է 4-րդ քայլը:
  4. Հեռացրեք մի հանգույց հերթից, թող լինի ընթացիկ հանգույց: Եթե ​​ընթացիկ հանգույցի ձախ երեխան զրոյական չէ, ստուգեք, արդյոք գտել է, որ NonComplete- ը ճիշտ է, եթե այո կեղծ վերադարձեք, այլապես ձախ երեխային հերթ կանգնեցրեք, եթե ձախ երեխան զրոյական է, գտեք NonComplete- ը որպես ճշմարիտ: Նմանապես, եթե ճիշտ երեխան զրոյական չէ, ստուգեք ՝ արդյոք գտել է, որ Ոչ ճիշտ է, եթե այո կեղծ է վերադարձնում, այլապես աջ երեխային հերթ կանգնեցրեք, եթե աջ երեխան հայտնաբերված է ոչ լրիվ, քանի որ ճիշտ է:
  5. Եթե ​​հասնենք 5-րդ քայլին, վերադարձիր իրական:

Կոդ

Java կոդ ՝ ստուգելու համար, որ տվյալ Երկուական ծառը ամբողջական է, թե ոչ

import java.util.LinkedList;
import java.util.Queue;
class CheckWhetherAGivenBinaryTreeIsCompleteOrNot {
    // class representing the node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static boolean isComplete(Node root) {
        // if root is null, return true
        if (root == null) {
            return true;
        }

        // create a queue to do level order traversal
        Queue<Node> queue = new LinkedList<>();
        // add the root node to queue
        queue.add(root);
        // initialize foundNonComplete as false
        boolean foundNonComplete = false;

        while (!queue.isEmpty()) {
            // remove a node from queue
            Node curr = queue.poll();
            if (curr.left != null) {
                // if a non complete node was found, return false
                if (foundNonComplete) {
                    return false;
                }
                // add the left child to queue
                queue.add(curr.left);
            } else {
                // if left child is null, this is a non complete node
                foundNonComplete = true;
            }

            if (curr.right != null) {
                // if a non complete node was found, return false
                if (foundNonComplete) {
                    return false;
                }
                // add the right child to queue
                queue.add(curr.right);
            } else {
                // if right child is null, this is a non complete node
                foundNonComplete = true;
            }
        }

        // reaching here means tree is complete
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        Node root1 = new Node(1);
        root1.left = new Node(2);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(5);
        System.out.println(isComplete(root1));

        // Example 2
        Node root2 = new Node(9);
        root2.left = new Node(8);
        root2.right = new Node(14);
        root2.left.left = new Node(10);
        root2.right.right = new Node(2);
        System.out.println(isComplete(root2));
    }
}
true
false

C ++ կոդ ՝ ստուգելու համար, որ տվյալ Երկուական ծառը ամբողջական է, թե ոչ

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

// class representing the node of a binary tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

bool isComplete(Node *root) {
    // if root is null, return true
    if (root == NULL) {
        return true;
    }
    
    // create a queue to do level order traversal
    queue<Node*> q;
    // add the root node to queue
    q.push(root);
    // initialize foundNonComplete as false
    bool foundNonComplete = false;
    
    while (!q.empty()) {
        // remove a node from queue
        Node *curr = q.front();
        q.pop();
        if (curr->left != NULL) {
            // if a non complete node was found, return false
            if (foundNonComplete)
                return false;
            // add the left child to queue
            q.push(curr->left);
        } else {
            // if left child is null, this is a non complete node
            foundNonComplete = true;
        }
        
        if (curr->right != NULL) {
            // if a non complete node was found, return false
            if (foundNonComplete) 
                return false;
            q.push(curr->right);
        }
    }
    
    // reaching here means tree is complete
    return true;
}

int main() {
    // Example 1
    Node *root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(5);
    if (isComplete(root1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    Node *root2 = new Node(9);
    root2->left = new Node(8);
    root2->right = new Node(14);
    root2->left->left = new Node(10);
    root2->right->right = new Node(2);
    if (isComplete(root2)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք կատարել ենք միայն երկուական ծառի մակարդակի կարգի անցում: Մակարդակի կարգի անցումը անցնում է ծառի հանգույցների միջով: Այսպիսով, ալգորիթմը գործում է գծային ժամանակի բարդության մեջ:

Տիեզերական բարդություն

ՎՐԱ), մակարդակի կարգի անցումը պահանջում է հերթի օգտագործում, ինչը ստիպում է ալգորիթմին գծային տարածական բարդություն ունենալ: