N-ағаш ағашындағы берілген түйіннің бауырларының саны  


Күрделілік дәрежесі қиын
Жиі кіреді Amazon Bloomberg CodeNation Google
N-ағашы кезек іздеу ағаш Ағаштарды кесу

Проблемалық мәлімдеме  

«N-ary ағашындағы берілген түйіннің бауырларының саны» мәселесі сізге n-ary ағашы мен мақсатты түйін берілгенін айтады. Мақсатты түйіннің бауырларының санын табыңыз. Түйін әрдайым ағашта болады және бірінші түйін ағаштың тамыры деп есептейік.

мысал  

енгізу

N-ағаш ағашындағы берілген түйіннің бауырларының санытүйреуіш

түйін = 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 мәнін қайтарыңыз.
Сондай-ақ, қараңыз
M элементті алып тастағаннан кейін ерекше элементтердің минималды саны

код  

N-ary ағашындағы берілген түйіннің бауырларының санын табуға арналған Java коды

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

N-ary ағашында берілген түйіннің бауырларының санын табу үшін C ++ коды

#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

Күрделілікті талдау  

Уақыттың күрделілігі

O (N), өйткені біз ағаш үшін BFS жасадық. Біз алгоритмді сызықтық уақытта іске қосатын барлық түйіндерді араладық.

Сондай-ақ, қараңыз
Кезекті ауыстыру

Ғарыштың күрделілігі

O (N), BFS кезегін пайдалану бізге сызықтық кеңістікті қажет етеді. Сонымен алгоритмнің кеңістік күрделілігі O (N) құрайды.