შეამოწმეთ არის მოცემული ორობითი ხე სრული თუ არა  


Რთული ტური Hard
ხშირად ეკითხებიან ალაცია American Express მონაცემთა ბაზები ოქსიგენის საფულე Spotify
ორობითი ხე Queue ხე

პრობლემის განცხადება  

პრობლემა "შეამოწმეთ არის დასრულებული თუ არა მოცემული ორობითი ხე" აცხადებს, რომ თქვენ გეძლევათ ორობითი ხის ფესვი, შეამოწმეთ ხე დასრულებულია თუ არა. Binary Tree– ს სრული დონეები აქვს შევსებული, გარდა ბოლო დონისა და ბოლო დონის კვანძები რაც შეიძლება მეტი დარჩა.

მაგალითები  

შეყვანის

შეამოწმეთ არის მოცემული ორობითი ხე სრული თუ არა

true

შეყვანის

შეამოწმეთ არის მოცემული ორობითი ხე სრული თუ არა

false

მიდგომა  

A სრული ორობითი ხე არის ორობითი ხე რომელშიც ყველა დონე ივსება, გარდა ბოლო დონისა და ბოლო დონის კვანძები რაც შეიძლება მეტი დარჩა.

იმის შესამოწმებლად, ორობითი ხე დასრულებულია თუ არა, შეგვიძლია გამოვიყენოთ დონის შეკვეთის გადაკვეთა ხის.

  1. განსაზღვრეთ სრული კვანძი, როგორც კვანძი, რომელსაც აქვს მარცხენა და მარჯვენა ბავშვი, როგორც არ არის null.
  2. სრული ხისთვის, თუ დონის შეკვეთის გადაკვეთის დროს ვხედავთ არასრულ კვანძს, ამ კვანძის შემდეგ ყველა კვანძი უნდა იყოს ფოთლის კვანძი, წინააღმდეგ შემთხვევაში ხე არ არის დასრულებული.
  3. ასევე, თუ არსებობს მარჯვენა კვანძი, რომელსაც აქვს null და მარცხენა ბავშვი null, ხე არ არის დასრულებული.

ალგორითმი

  1. თუ ფესვი ნულოვანია, დაბრუნდი true.
  2. შექმენით რიგი და დააჭირეთ მას ძირეული კვანძი. იძებნება ლოგიკური ცვლადის ინიციალიზაცია, როგორც არასწორი, არასწორი.
  3. მიუხედავად იმისა, რომ რიგი ცარიელი არ არის, გაიმეორეთ 4 ნაბიჯი.
  4. ამოიღეთ კვანძი რიგიდან, დაე იყოს ის მიმდინარე კვანძი. თუ ამჟამინდელი კვანძის მარცხენა შვილი ნულოვანი არ არის, შეამოწმეთ არის თუ არა ნაპოვნიNonComplete მართალია, თუ დიახ დაუბრუნეთ false, სხვა შემთხვევაში დააჭირეთ მარცხნივ ბავშვს რიგში, თუ მარცხენა ბავშვი null, იპოვნეთ NotComplete როგორც ნამდვილი. ანალოგიურად, თუ სწორი ბავშვი არ არის ნულოვანი, შეამოწმეთ არის თუ არა findNonComplete სიმართლე, თუ დიახ დაუბრუნეთ false, სხვა შემთხვევაში დააყენეთ სწორი ბავშვი რიგში, თუ სწორი ბავშვი არის null ნიშნის ნაპოვნი NonComplete როგორც ნამდვილი.
  5. თუ მე -5 ნაბიჯს მივაღწიეთ, დაბრუნდი ჭეშმარიტი.
იხილეთ ასევე
ააშენეთ BST მოცემული დონის შეკვეთის გადაკვეთისგან

კოდი  

ჯავის კოდი იმისთვის, რომ შეამოწმოთ არის მოცემული ორობითი ხე სრული თუ არა

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

სირთულის ანალიზი  

დროის სირთულე

O (N), როგორც ჩვენ მხოლოდ გავაკეთეთ ორობითი ხის დონის ორდერის გადაკვეთა. დონის შეკვეთის გადაკვეთა გადის ხის კვანძებში. ამრიგად, ალგორითმი მუშაობს ხაზოვანი დროის სირთულეში.

იხილეთ ასევე
შეაერთეთ ორი BST შეზღუდული დამატებითი ადგილით

სივრცის სირთულე

O (N), დონის შეკვეთის გადაკვეთა მოითხოვს რიგის გამოყენებას, რაც ალგორითმს ხაზოვანი სივრცის სირთულეს ანიჭებს.