מספר אחים של צומת נתון בעץ n-ary


רמת קושי קשה
נשאל לעתים קרובות אמזון בעברית בלומברג CodeNation Google
N-ary-tree תור חיפוש עֵץ מעבר עץ

הצהרת בעיה

הבעיה "מספר אחים של צומת נתון בעץ n-ary" קובעת שאתה מקבל עץ n-ary וצומת יעד. מצא את מספר האחים של צומת היעד. נניח שצומת תמיד קיים בעץ והצומת הראשון הוא שורש העץ.

דוגמה

קֶלֶט

מספר אחים של צומת נתון בעץ n-ary

צומת = 10
צומת = 11

3
1

הסבר
אחים של עשרה הם {10, 41, 6}
אחים של 11 הם {9}

אַלגוֹרִיתְם

אחים של צומת הם הצמתים הנמצאים באותה רמה כמו הצומת הנתון, או במילים אחרות, אחים של צומת הם אחד פחות ממספר הילדים של ההורה שלו.

שקול את עץ בדוגמה לעיל, ותן לצומת להיות 10
הורה של 10 = 51
ילדים בני 51 הם {10, 41, 32, 6}
אחים ל -10 הם ילדים מההורה שלה למעט 10, כלומר אחים ל -10 הם {41, 32, 6}

נקודה חשובה: מספר האחים של השורש הוא 0. מכיוון שאין הורה לשורש.

הרעיון למצוא את מספר האחים של הצומת הוא לעשות BFS על העץ הנתון, אם ילדי הצומת זהים לצומת הנתון, החזר (מספר הילדים של הצומת הזה - 1).

  1. אם הצומת הנתון שווה לשורש או שורש הוא null, החזר 0.
  2. צור תור של צמתים עבור BFS ולדחוף את השורש לתור.
  3. בעוד שהתור אינו ריק חזור על שלב 4.
  4. הסר אלמנט מהתור, חצה את כל ילדי האלמנט הנוכחי, אם מישהו מילדיו שווה לצומת הנתון, החזר (מספר הילדים של הצומת הנוכחי - 1), אחרת דחף את הילדים לתור.
  5. אם אין צומת התואם לצומת הנתון, חזור -1.

קופונים

קוד Java למציאת מספר האחים של צומת נתון בעץ 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

קוד C ++ למציאת מספר האחים של צומת נתון בעץ n-ary

#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).