N-ary ਲੜੀ ਵਿੱਚ ਦਿੱਤੇ ਗਏ ਨੋਡ ਦੇ ਭੈਣਾਂ-ਭਰਾਵਾਂ ਦੀ ਸੰਖਿਆ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਬਲੂਮਬਰਗ ਕੋਡਨੇਸ਼ਨ ਗੂਗਲ
ਐਨ-ਐਰੀ-ਟ੍ਰੀ ਕਤਾਰ ਖੋਜ ਕਰਨਾ ਟ੍ਰੀ ਟ੍ਰੀ ਟ੍ਰੈਵਲ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ "ਐਨ-ਐਰੀ ਟ੍ਰੀ ਵਿੱਚ ਦਿੱਤੇ ਗਏ ਨੋਡ ਦੇ ਭੈਣਾਂ-ਭਰਾਵਾਂ ਦੀ ਸੰਖਿਆ" ਦੱਸਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਇੱਕ ਐਨ-ਆਰਰੀ ਲੜੀ ਅਤੇ ਇੱਕ ਨਿਸ਼ਾਨਾ ਨੋਡ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ. ਟਾਰਗੇਟ ਨੋਡ ਦੇ ਭੈਣਾਂ-ਭਰਾਵਾਂ ਦੀ ਸੰਖਿਆ ਲੱਭੋ. ਮੰਨ ਲਓ ਕਿ ਨੋਡ ਹਮੇਸ਼ਾ ਰੁੱਖ ਵਿਚ ਮੌਜੂਦ ਹੁੰਦਾ ਹੈ ਅਤੇ ਪਹਿਲਾ ਨੋਡ ਰੁੱਖ ਦੀ ਜੜ ਹੈ.

ਉਦਾਹਰਨ

ਇੰਪੁੱਟ

N-ary ਲੜੀ ਵਿੱਚ ਦਿੱਤੇ ਗਏ ਨੋਡ ਦੇ ਭੈਣਾਂ-ਭਰਾਵਾਂ ਦੀ ਸੰਖਿਆ

ਨੋਡ = 10
ਨੋਡ = 11

3
1

ਕਥਾ
10 ਦੇ ਭੈਣ-ਭਰਾ {41, 6, 32 are ਹਨ
11 ਦੇ ਭੈਣ ਭਰਾ {9 are ਹਨ

ਐਲਗੋਰਿਥਮ

ਨੋਡ ਦੇ ਭੈਣ-ਭਰਾ ਦਿੱਤੇ ਗਏ ਨੋਡ ਦੇ ਸਮਾਨ ਪੱਧਰ ਤੇ ਨੋਡ ਹੁੰਦੇ ਹਨ, ਜਾਂ ਦੂਜੇ ਸ਼ਬਦਾਂ ਵਿਚ, ਨੋਡ ਦੇ ਭੈਣ-ਭਰਾ ਉਸਦੇ ਮਾਂ-ਪਿਓ ਦੇ ਬੱਚਿਆਂ ਦੀ ਗਿਣਤੀ ਤੋਂ ਘੱਟ ਹੁੰਦੇ ਹਨ.

ਜ਼ਰਾ ਸੋਚੋ ਰੁੱਖ ਨੂੰ ਉਪਰੋਕਤ ਉਦਾਹਰਣ ਵਿੱਚ, ਅਤੇ ਨੋਡ 10 ਹੋਣ ਦਿਓ
10 = 51 ਦੇ ਮਾਪੇ
51 ਦੇ ਬੱਚੇ 10 ਡਾਲਰ, 41, 32, 6 are ਹਨ
10 ਦੇ ਭੈਣ-ਭਰਾ 10 ਨੂੰ ਛੱਡ ਕੇ ਇਸਦੇ ਮਾਪਿਆਂ ਦੇ ਬੱਚੇ ਹਨ, ਭਾਵ, 10 ਦੇ ਭੈਣ-ਭਰਾ 41 ਡਾਲਰ, 32, 6} ਹਨ

ਮਹੱਤਵਪੂਰਨ ਬਿੰਦੂ: ਰੂਟ ਦੇ ਭੈਣਾਂ-ਭਰਾਵਾਂ ਦੀ ਗਿਣਤੀ 0 ਹੈ. ਕਿਉਂਕਿ ਜੜ ਦਾ ਕੋਈ ਮਾਪਾ ਨਹੀਂ ਹੁੰਦਾ.

ਨੋਡ ਦੇ ਭੈਣਾਂ-ਭਰਾਵਾਂ ਦੀ ਸੰਖਿਆ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਇਹ ਦਰਸਾਏ ਗਏ ਦਰੱਖਤ ਤੇ ਇੱਕ ਬੀਐਫਐਸ ਕਰਨਾ ਹੈ, ਜੇ ਨੋਡ ਦੇ ਬੱਚੇ ਦਿੱਤੇ ਗਏ ਨੋਡ ਦੇ ਸਮਾਨ ਹਨ, ਵਾਪਸੀ (ਉਸ ਨੋਡ ਦੇ ਬੱਚਿਆਂ ਦੀ ਗਿਣਤੀ - 1).

  1. ਜੇ ਦਿੱਤਾ ਹੋਇਆ ਨੋਡ ਰੂਟ ਦੇ ਬਰਾਬਰ ਹੈ ਜਾਂ ਰੂਟ ਨਿਰਬਲ ਹੈ, ਤਾਂ 0 ਵਾਪਸ ਕਰੋ.
  2. ਲਈ ਨੋਡਾਂ ਦੀ ਇੱਕ ਕਤਾਰ ਬਣਾਓ BFS ਅਤੇ ਜੜ ਨੂੰ ਕਤਾਰ ਵੱਲ ਧੱਕੋ.
  3. ਜਦੋਂ ਕਿ ਕਤਾਰ ਖਾਲੀ ਨਹੀਂ ਦੁਹਰਾਓ ਕਦਮ 4.
  4. ਇੱਕ ਤੱਤ ਨੂੰ ਕਤਾਰ ਤੋਂ ਹਟਾਓ, ਮੌਜੂਦਾ ਤੱਤ ਦੇ ਸਾਰੇ ਬੱਚਿਆਂ ਨੂੰ ਪਾਰ ਕਰੋ, ਜੇ ਇਸਦਾ ਕੋਈ ਵੀ ਬੱਚਾ ਦਿੱਤੇ ਨੋਡ ਦੇ ਬਰਾਬਰ ਹੈ, ਵਾਪਸ ਆਓ (ਮੌਜੂਦਾ ਨੋਡ - 1 ਦੇ ਬੱਚਿਆਂ ਦੀ ਗਿਣਤੀ), ਨਹੀਂ ਤਾਂ ਬੱਚਿਆਂ ਨੂੰ ਕਤਾਰ ਵਿੱਚ ਧੱਕੋ.
  5. ਜੇ ਦਿੱਤੇ ਨੋਡ ਨਾਲ ਮੇਲ ਖਾਂਦਾ ਕੋਈ ਨੋਡ ਨਹੀਂ ਹੈ, ਤਾਂ ਵਾਪਸ ਆਓ -1.

ਕੋਡ

ਜਾਵਾ ਕੋਡ n-ary ਲੜੀ ਵਿੱਚ ਦਿੱਤੇ ਗਏ ਨੋਡ ਦੇ ਭੈਣਾਂ-ਭਰਾਵਾਂ ਦੀ ਗਿਣਤੀ ਲੱਭਣ ਲਈ

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

ਐਨ + ਐਰੀ ਲੜੀ ਵਿਚ ਦਿੱਤੇ ਗਏ ਨੋਡ ਦੇ ਭੈਣਾਂ-ਭਰਾਵਾਂ ਦੀ ਗਿਣਤੀ ਲਈ ਸੀ ++ ਕੋਡ

#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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਦਰੱਖਤ ਲਈ ਬੀ.ਐੱਫ.ਐੱਸ. ਅਸੀਂ ਹੁਣੇ ਹੁਣੇ ਸਾਰੇ ਨੋਡਾਂ ਤੋਂ ਪਾਰ ਲੰਘੇ ਹਨ ਜੋ ਐਲਗੀਰਿਦਮ ਨੂੰ ਲੰਬੇ ਸਮੇਂ ਵਿਚ ਚਲਾਉਣ ਲਈ ਬਣਾਉਂਦੇ ਹਨ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਬੀਐਫਐਸ ਲਈ ਕਤਾਰ ਦੀ ਵਰਤੋਂ ਕਰਨ ਨਾਲ ਸਾਡੇ ਲਈ ਰੇਖਿਕ ਜਗ੍ਹਾ ਖਰਚੀ ਗਈ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਐਲਗੋਰਿਦਮ ਦੀ ਸਪੇਸ ਗੁੰਝਲਤਾ ਹੈ ਓ (ਐਨ).