Берілген екілік ағаштың ата-бабаларын табудың итерациялық әдісі


Күрделілік дәрежесі орта
Жиі кіреді Adobe Amazon Фуркиттер Google InfoEdge Морган Стэнли Paytm Samsung
үйме ағаш

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

«Берілгеннің арғы аталарын табудың итеративті әдісі екілік ағаш”Проблемасында сізге екілік ағаш және кілтті көрсететін бүтін сан берілгендігі көрсетілген. Берілген кілттің барлық ата-бабаларын итерация көмегімен басып шығару функциясын жасаңыз.

Берілген екілік ағаштың ата-бабаларын табудың итерациялық әдісі

мысал

енгізу 

Берілген екілік ағаштың ата-бабаларын табудың итерациялық әдісі

кілт = 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) ішіне енгізуге / іздеуге / жоюға мүмкіндік беретіндіктен. Біз бұл мәселені уақыттың сызықтық күрделілігінде шеше аламыз. Төмендегі шешімде біз іздеу сызбасын тәсіл ретінде қолданамыз торап бүкіл ағаш. Қозғалыс кезінде біз әр түйіннің ата-анасын сақтаймыз. Содан кейін біз ата-бабаларды басып шығару үшін (ата-аналарды сақтайтын) картамыздан өтіп, функция жасадық. шешім барлық уақыттың сызықтық күрделілігінде жүреді O (N).

код

Берілген екілік ағаштың ата-бабаларын табуға арналған Итеративті әдіске арналған 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

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

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

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

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

O (N) өйткені біз unordered_map және stack-те қосымша орынды пайдаландық.