የተሰጠው የሁለትዮሽ ዛፍ ቅድመ አያቶችን ለማግኘት ኢተራዊ ዘዴ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የ 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.

እዚህ ለዚህ ችግር እኛ የሁለትዮሽ ዛፍ ተሰጠን የመስቀለኛ መንገድ ቅድመ አያቶችን ማተም ያስፈልገናል ፡፡ ልክ የመስቀለኛ መንገድ ልጆች እንዳሉን ሁሉ ከዛፉ ሥር በስተቀር ቅድመ አያቱ አለን ፡፡ የዛፍ ቅጠሎችን ካገናዘቡ ልጆች የላቸውም ፡፡ በተመሳሳይም የስር መስቀለኛ መንገድ ቅድመ አያት የለውም ፡፡ እዚህ የእያንዳንዱን መስቀለኛ መንገድ ወላጅ እናከማቻለን ፡፡ ስለዚህ ቅድመ አያቶቹን ማተም ሲያስፈልገን ፡፡ ቅድመ አያቶቻቸውን ለማግኘት ወላጆቹን እንጠቀማለን ፡፡ እኛ አንድ ተጠቅመናል ያልተስተካከለ_ካርታ / 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

የተሰጠው የሁለትዮሽ ዛፍ ቅድመ አያቶችን ለማግኘት የጃቫ ፕሮግራም ለአይቴራላዊ ዘዴ

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 በተሰጠው ዛፍ ውስጥ የአንጓዎች ቁጥር የት ነው? እኛ ገና በጠቅላላው ዛፍ ላይ ተሻግረን አንዴ አባቶችን ለማተም በካርታው ላይ ከተጓዝን ፡፡

የቦታ ውስብስብነት

ኦ (ኤን) ምክንያቱም ባልተመዘገበ_ካርታ እና በቁልል ውስጥ ተጨማሪ ቦታ እንጠቀም ነበር ፡፡