Итеративна метода за наоѓање предци на дадено бинарно дрво


Ниво на тешкотија Медиум
Често прашувано во Adobe Амазон Фуркити Google ИнфоЕџ Морган Стенли Исплата 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.

Овде, за овој проблем, ни е дадено бинарно дрво и треба да отпечатиме предци на јазол. Исто како што имаме деца од јазол, и ние го имаме неговиот предок освен коренот на дрвото. Ако ги земете предвид лисјата на дрвото, тие немаат деца. Слично на тоа, коренскиот јазол нема предок. Тука го чуваме родителот на секој јазол. Така што кога треба да ги испечатиме неговите предци. Useе ги искористиме родителите за да ги најдеме нивните предци. Користевме ан unordered_map / HashSet да се изврши оваа операција. Бидејќи HashSet дозволува вметнување / пребарување / бришење во О (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 е бројот на јазли во даденото стебло. Само што поминавме низ целото дрво и еднаш ја прегазивме картата за да ги испечатиме предците.

Комплексноста на просторот

НА) затоа што искористивме дополнителен простор во unordered_map и stack.