Տրված հանգույցի քույրերի և եղբայրների քանակը ծառի ծառում


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Amazon Bloomberg CodeNation Google
N-ary- ծառ Հերթ Որոնում ծառ Reeառի անցում

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

«Տվյալ հանգույցի քույրերի և եղբայրների թիվը n-ary Tree- ում» խնդիրը նշում է, որ ձեզ տրվում է n-ary Tree և նպատակային հանգույց: Գտեք թիրախային հանգույցի եղբայրների և քույրերի թիվը: Ենթադրենք, որ հանգույցը միշտ առկա է ծառի մեջ, իսկ առաջին հանգույցը ծառի արմատն է:

Օրինակ

Մուտքային

Տրված հանգույցի քույրերի և եղբայրների քանակը ծառի ծառում

հանգույց = 10
հանգույց = 11

3
1

բացատրություն
10-ի քույրերը {41, 6, 32} են
11-ի եղբայրները {9} են

Ալգորիթմ

Հանգույցի քույրեր և քույրեր այն հանգույցներն են, որոնք առկա են տրված հանգույցի նույն մակարդակում, կամ այլ կերպ ասած ՝ հանգույցի եղբայրներ և քույրեր մեկով պակաս են իր ծնողի երեխաների թվից:

Դիտարկենք այն ծառ վերը նշված օրինակում և թող հանգույցը լինի 10
10 = 51-ի ծնող
51 տարեկան երեխաները {10, 41, 32, 6} տարեկան են
10-ի քույրերն ու քույրերը ծնողի երեխաներ են, բացառությամբ 10-ի, այսինքն ՝ 10-ի քույրեր և եղբայրներ ՝ {41, 32, 6}

Կարևոր կետԱրմատի քույրերի և եղբայրների թիվը 0. է: Քանի որ արմատից ծնող չկա:

Հանգույցի քույրերի և քույրերի թիվը գտնելու գաղափարը տվյալ ծառի վրա կատարել BFS, եթե հանգույցի երեխաները նույնն են, ինչ տվյալ հանգույցը, վերադարձը (այդ հանգույցի երեխաների թիվը `1):

  1. Եթե ​​տրված հանգույցը հավասար է արմատին կամ արմատը զրոյական է, վերադարձիր 0:
  2. Ստեղծեք հանգույցների հերթ BFS և արմատը մղել դեպի հերթը:
  3. Չնայած հերթը դատարկ չէ, կրկնում է 4-րդ քայլը:
  4. Հեռացրեք մի տարր հերթից, անցեք ընթացիկ տարրի բոլոր երեխաների միջով, եթե նրա երեխաներից յուրաքանչյուրը հավասար է տվյալ հանգույցին, վերադարձեք (ընթացիկ հանգույցի երեխաների քանակը `1), այլապես երեխաներին մղեք հերթ:
  5. Եթե ​​տվյալ հանգույցին համապատասխանող հանգույց չկա, վերադարձիր -1:

Կոդ

Java օրենսգիրք ՝ տրված հանգույցի քույրերի և եղբայրների թիվը n-ary Tree- ում գտնելու համար

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class NumberOfSiblingsOfAGivenNodeInNAryTree {
    // class representing node of n-ary tree
    static class Node {
        
        ArrayList<Node> child;
        int data;
        public Node(int data) {
            this.data = data;
            this.child = new ArrayList<>();
        }
    }

    private static int siblings(Node root, int target) {
        // if the given node is equals to the root or root is null, return 0
        if (root == null || root.data == target) {
            return 0;
        }

        // create a queue of nodes
        Queue<Node> queue = new LinkedList<>();
        // push the root to queue
        queue.add(root);

        // do a BFS of the tree
        while (!queue.isEmpty()) {
            // remove one element from the queue
            Node curr = queue.poll();
            // traverse its children
            for (int i = 0; i < curr.child.size(); i++) {
                // current child
                Node currChild = curr.child.get(i);
                // if current child is the target, return (parent's children count - 1)
                if (currChild.data == target) {
                    return (curr.child.size() - 1);
                }
                // add the child to the queue
                queue.add(currChild);
            }
        }

        // if there is no match, return -1
        return -1;
    }

    public static void main(String[] args) {
        // Example n-ary tree
        Node root = new Node(51);
        // children of 51
        root.child.add(new Node(10));
        root.child.add(new Node(41));
        root.child.add(new Node(6));
        root.child.add(new Node(32));
        // children of 10
        root.child.get(0).child.add(new Node(53));
        // children of 41
        root.child.get(1).child.add(new Node(95));
        // children of 6
        root.child.get(2).child.add(new Node(28));
        // children of 32
        root.child.get(3).child.add(new Node(9));
        root.child.get(3).child.add(new Node(11));
        // children of 53
        root.child.get(0).child.get(0).child.add(new Node(5));
        root.child.get(0).child.get(0).child.add(new Node(7));
        // children of 11
        root.child.get(3).child.get(1).child.add(new Node(3));
        root.child.get(3).child.get(1).child.add(new Node(8));

        System.out.println(siblings(root, 10));
        System.out.println(siblings(root, 11));
    }
}
3
1

C ++ կոդ ՝ տրված հանգույցի քույրերի և եղբայրների թիվը n-ary Tree- ում գտնելու համար

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

// class representing node of a n-ary tree
class Node {
    public:
    int data;
    vector<Node*> child;
    
    Node(int d) {
        data = d;
    }
};

int siblings(Node *root, int target) {
    // if the given node is equals to the root or root is null, return 0
    if (root == NULL || root->data == target) {
        return 0;
    }
    
    // create a queue of nodes
    queue<Node*> q;
    // push the root to queue
    q.push(root);
    
    // do a BFS of the tree
    while (!q.empty()) {
        // remove one element from the queue
        Node *curr = q.front();
        q.pop();
        // traverse its children
        for (int i = 0; i < curr->child.size(); i++) {
            // current child
            Node *currChild = curr->child[i];
            // if current child is the target, return (parent's children count - 1)
            if (currChild->data == target) {
                return (curr->child.size() - 1);
            }
            // add the child to the queue
            q.push(curr->child[i]);
        }
    }
    
    // if there is no match, return -1
    return -1;
}

int main() {
    // Example n-ary tree
    Node *root = new Node(51);
    // children of 51
    root->child.push_back(new Node(10));
    root->child.push_back(new Node(41));
    root->child.push_back(new Node(6));
    root->child.push_back(new Node(32));
    // children of 10
    root->child[0]->child.push_back(new Node(53));
    // children of 41
    root->child[1]->child.push_back(new Node(95));
    // children of 6
    root->child[2]->child.push_back(new Node(28));
    // children of 32
    root->child[3]->child.push_back(new Node(9));
    root->child[3]->child.push_back(new Node(11));
    // children of 53
    root->child[0]->child[0]->child.push_back(new Node(5));
    root->child[0]->child[0]->child.push_back(new Node(7));
    // children of 11
    root->child[3]->child[1]->child.push_back(new Node(3));
    root->child[3]->child[1]->child.push_back(new Node(8));

    cout<<siblings(root, 10)<<endl;
    cout<<siblings(root, 11)<<endl;
    
    return 0;
}
3
1

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

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

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

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

ՎՐԱ), BFS- ի համար հերթի օգտագործումը մեզ համար գծային տարածություն է արժեցել: Այսպիսով, ալգորիթմի տիեզերական բարդությունը O է (N):