Təkrarlanan alt ağacları tapın

Subtrees təkrarlayın 

Alt ağacların eyni qovşaq dəyərlərinə və quruluşuna sahib olduqları təqdirdə təkrarlandığı deyilir. Verilmişdir ikili ağac qovşaqlarla. Bütün təkrarlanan alt ağacları tapın və kök düyünlərini qaytarın.

Pin

misal

Pin

Burada 4 və 2-> 4 alt ağacları birdən çox görünür, buna görə də hər iki alt ağacın kök qovşaqlarını, yəni 4 və 2-ni qaytaracağıq.

Pin

Burada subtree 4 dəfədən çox görünür, buna görə alt ağacın kök düyününü, yəni 4'ü qaytaracağıq.

Hashmap Metodundan istifadə

Dublikat Subtrees tapmaq üçün alqoritm

1. İkili bir ağacı başladın.
2. Simli və int tiplərini saxlamaq üçün sıralanmamış bir xəritə yaradın.
3. Düyün boşdursa, boş simli qaytarın.
4. Düyünlərin dəyərlərini a sim onları simli tipə çevirməklə.
5. Xəritədə bir sətir dəyərinin mövcud olub olmadığını yoxlayın, yəni xəritə [sətir] düyünün dəyərinin bir çapa bərabərdir.
6. Xəritədəki başqa artım dəyəri 1.
7. Sətri qayıt.

Zamanın mürəkkəbliyi: O (n ^ 2), burada n ikili ağacdakı qovşaqların sayıdır. Hər bir nodu bir dəfə ziyarət edirik, lakin yaradılış O (n) O (n) işini ala bilər, buna görə zaman mürəkkəbliyi O (n ^ 2) -dir.

Kosmik Mürəkkəblik: O (n ^ 2), hashmap və ağacın yaradılması üçün istifadə olunan yerdir.

C ++ Proqramı

#include <bits/stdc++.h> 
using namespace std; 
  
struct Node{ 
    int value; 
    struct Node* left, *right; 
}; 
  
string inorder(Node* node, unordered_map<string, int>& m){ 
    if(!node) 
        return ""; 
  
    string str = "("; 
    str += inorder(node->left, m); 
    str += to_string(node->value); 
    str += inorder(node->right, m); 
    str += ")"; 
  
    if(m[str] == 1) 
        cout << node->value << " "; 
  
    m[str]++; 
  
    return str; 
} 
  
void Duplicates(Node* root){ 
    unordered_map<string, int> m; 
    inorder(root, m); 
} 
  
Node* newNode(int data){ 
    Node* temp = new Node; 
    temp->value = data; 
    temp->left = temp->right = NULL; 
    return temp; 
} 
  
int main(){
    
    Node* root = NULL; 
    root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->right->left = newNode(2); 
    root->right->left->left = newNode(4); 
    root->right->right = newNode(4); 
    Duplicates(root); 
    
    return 0; 
}

4 2

Java Proqramı

import java.util.HashMap; 

class Duplicate_subtress{ 
  
    static HashMap<String, Integer> m; 
    
    static class Node{ 
        int data; 
        Node left; 
        Node right; 
        Node(int data){ 
            this.data = data; 
            left = null; 
            right = null; 
        } 
    } 
    
    static String inorder(Node node){ 
        if(node == null) 
            return ""; 
       
        String str = "("; 
        str += inorder(node.left); 
        str += Integer.toString(node.data); 
        str += inorder(node.right); 
        str += ")"; 
       
        if(m.get(str) != null && m.get(str)==1 ) 
            System.out.print( node.data + " "); 
       
        if(m.containsKey(str)) 
            m.put(str, m.get(str) + 1); 
        else
            m.put(str, 1); 
          
        return str; 
    } 
       
    static void Duplicates(Node root){ 
        m = new HashMap<>(); 
        inorder(root); 
    }  
    
    public static void main(String args[]){
        
        Node root = null; 
        root = new Node(1); 
        root.left = new Node(2); 
        root.right = new Node(3); 
        root.left.left = new Node(4); 
        root.right.left = new Node(2); 
        root.right.left.left = new Node(4); 
        root.right.right = new Node(4); 
        Duplicates(root); 
        
    } 
}

4 2

References