שיטה איטרטיבית למציאת אבות קדומים של עץ בינארי נתון


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית פורקיטים Google InfoEdge מורגן סטנלי Paytm סמסונג
לערום עֵץ

הצהרת בעיה

"שיטה איטרטיבית למצוא אבות קדומים של נתון עץ בינאריהבעיה קובעת שאתה מקבל עץ בינארי ומספר שלם המייצג מפתח. צור פונקציה להדפסת כל אבותיו של המפתח הנתון באמצעות איטרציה.

שיטה איטרטיבית למציאת אבות קדומים של עץ בינארי נתון

דוגמה

קֶלֶט 

שיטה איטרטיבית למציאת אבות קדומים של עץ בינארי נתון

מפתח = 6

5 2 1

הסבר: הנתיב מהשורש לצומת בעל הערך 6 הוא 1 2 5 6. לכן רצף האב מ- 6 לשורש הוא 5 2 1.

קלט:

שיטה איטרטיבית למציאת אבות קדומים של עץ בינארי נתון

מפתח = 10

9 7 1

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

1. Create a structure Node which contains an integer variable to hold data and two pointers left and right of type Node.
2. After that, create the parameterized constructor of the structure which accepts an integer value as it's parameter. Store the integer value in the data variable of Node and initialize left and right pointers as null.
3. Create a function to print the tree path which accepts an unordered map and an integer variable key as it's a parameter. While the key variable is equal to the map[key], print the key.
4. Similarly, create another function to set the parents for all the nodes in the given binary tree which accepts a pointer to the root node and an unordered map as it's parameter.
5. Create a stack data structure of Node* type. Push/insert the root in the stack.
6. After that, traverse while the size of the stack is not 0. Create a pointer curr of type Node and store the element at the top of the stack in it and pop/delete it from the stack.
7. If the right of the curr is present, update the map at index data of right of curr as the data of curr. Push/insert the right of curr in the stack.
8. If the left of the curr is present, update the map at index data of the left of curr as the data of curr. Push/insert the left of curr in the stack.
9. Similarly, create another function to print the ancestors. Check if the root is equal to null, return.
10. Create an unordered map and set the data of its root as 0.
11. Call the function to set the parents of all nodes.
12. Finally, call the function to print the tree path.

כאן לבעיה זו, אנו מקבלים עץ בינארי ועלינו להדפיס אבות של צומת. בדיוק כמו שיש לנו ילדים של צומת, יש לנו את האב הקדמון שלו למעט שורש העץ. אם אתה מחשיב עלים של עץ, אין להם ילדים. באופן דומה, לצומת השורש אין אב קדמון. כאן אנו מאחסנים את האב של כל צומת. כך שכאשר אנו צריכים להדפיס את אבותיו. נשתמש בהורים כדי למצוא את אבותיהם. השתמשנו ב- unordered_map / HashSet לבצע פעולה זו. מכיוון שה- HashSet מאפשר הכנסה / חיפוש / מחיקה ב- O (1). אנו מסוגלים לפתור בעיה זו במורכבות זמן ליניארית. בפתרון שלהלן אנו משתמשים בגרף המחפש כמו גישה אליו לַחֲצוֹת את כל העץ. ותוך כדי חצייה אנו מאחסנים את ההורה של כל צומת. ואז יצרנו פונקציה תוך כדי מעבר על המפה שלנו (המאחסנת את ההורים) כדי להדפיס את האבות הקדמונים. הפתרון כולו פועל במורכבות זמן ליניארית של עַל).

קופונים

תוכנית C ++ לשיטה איטרטיבית למציאת אבות קדומים של עץ בינארי נתון

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

struct Node{
    int data;
    Node *left, *right;

    Node(int data){
        this->data = data;
        this->left = this->right = nullptr;
  }
};

void printTopToBottomPath(unordered_map<int, int> parent, int key){
    while(key = parent[key]){
        cout << key << " ";
    }
    cout << endl;
}

void setParent(Node* root, unordered_map<int, int> &parent){
    
    stack<Node*> stack;
    stack.push(root);

    while(!stack.empty()){
        
        Node* curr = stack.top();
        stack.pop();

        if(curr->right){
           parent[curr->right->data] = curr->data;
           stack.push(curr->right);
        }

        if(curr->left){
           parent[curr->left->data] = curr->data;
           stack.push(curr->left);
        }
    }
}

void printAncestors(Node* root, int node){
    
    if(root == nullptr){
        return;
    }

    unordered_map<int, int> parent;

    parent[root->data] = 0;

    setParent(root, parent);

    printTopToBottomPath(parent, node);
}

int main(){
    Node* root = nullptr;

    root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(7);
    root->left->left = new Node(3);
    root->left->right = new Node(5);
    root->right->left = new Node(8);
    root->right->right = new Node(9);
    root->left->left->left = new Node(4);
    root->left->right->right = new Node(6);
    root->right->right->left = new Node(10);

    int key = 6;
    printAncestors(root, key);

    return 0;
}
5 2 1

תוכנית Java לשיטה איטרטיבית למציאת אבות קדומים של עץ בינארי נתון

import java.util.*;

class Node{
  int data;
  Node left = null, right = null;

  Node(int data){
    this.data = data;
  }
}

class Main{
  
  public static void printTopToBottomPath(Map<Integer, Integer> parent, int key){
    while((key = parent.get(key)) != 0){
      System.out.print(key + " ");
    }
  }

  public static void setParent(Node root, Map<Integer, Integer> parent){
    
    Deque<Node> stack = new ArrayDeque<>();
    stack.add(root);

    while(!stack.isEmpty()){
      
      Node curr = stack.pollLast();

      if(curr.right != null){
        parent.put(curr.right.data, curr.data);
        stack.add(curr.right);
      }

      if(curr.left != null){
        parent.put(curr.left.data, curr.data);
        stack.add(curr.left);
      }
    }
  }

  public static void printAncestors(Node root, int node){
    
    if(root == null){
      return;
    }

    Map<Integer, Integer> parent = new HashMap<>();

    parent.put(root.data, 0);

    setParent(root, parent);

    printTopToBottomPath(parent, node);
  }

  public static void main(String[] args){
      
      Node root = new Node(1);
      root.left = new Node(2);
            root.right = new Node(7);
            root.left.left = new Node(3);
            root.left.right = new Node(5);
            root.right.left = new Node(8);
            root.right.right = new Node(9);
            root.left.left.left = new Node(4);
            root.left.right.right = new Node(6);
            root.right.right.left = new Node(10);

      int key = 6;
    
      printAncestors(root, key);
  }
}
5 2 1

ניתוח מורכבות

מורכבות זמן

עַל), כאשר N הוא מספר הצמתים בעץ הנתון. בדיוק עברנו על כל העץ ופעם עברנו מעל המפה כדי להדפיס אבות.

מורכבות בחלל

עַל) בגלל שהשתמשנו בשטח נוסף ב- unordered_map ובמחסנית.