ಎರಡು ಬೈನರಿ ಮರದ ಎಲ್ಲಾ ಹಂತಗಳು ಅನಗ್ರಾಮ್‌ಗಳೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ಪರಿಶೀಲಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಫೇಸ್ಬುಕ್ ಫ್ಯಾನಟಿಕ್ಗಳು ಫೋರ್‌ಕೈಟ್‌ಗಳು ಗ್ರೇ ಆರೆಂಜ್
ಅನಗ್ರಾಮ್ ಬೈನರಿ ಟ್ರೀ ಕ್ಯೂ ಮರ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಎರಡು ಬೈನರಿ ಮರದ ಎಲ್ಲಾ ಹಂತಗಳು ಅನಗ್ರಾಮ್‌ಗಳೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಿ” ನಿಮಗೆ ಎರಡು ಬೈನರಿ ಮರಗಳನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ, ಎರಡು ಮರಗಳ ಎಲ್ಲಾ ಹಂತಗಳು ಅನಗ್ರಾಮ್‌ಗಳೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಿ.

ಉದಾಹರಣೆಗಳು

ಇನ್ಪುಟ್

ಎರಡು ಬೈನರಿ ಮರದ ಎಲ್ಲಾ ಹಂತಗಳು ಅನಗ್ರಾಮ್‌ಗಳೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ಪರಿಶೀಲಿಸಿ

true

ಇನ್ಪುಟ್

ಎರಡು ಬೈನರಿ ಮರದ ಎಲ್ಲಾ ಹಂತಗಳು ಅನಗ್ರಾಮ್‌ಗಳೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ಪರಿಶೀಲಿಸಿ

false

ಎರಡು ಬೈನರಿ ಮರದ ಎಲ್ಲಾ ಹಂತಗಳು ಅನಗ್ರಾಮ್‌ಗಳೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸುವ ಅಲ್ಗಾರಿದಮ್

ನಾವು ಬಳಸುತ್ತೇವೆ ಹ್ಯಾಶಿಂಗ್ ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು. ಎರಡು ಹಂತಗಳಲ್ಲಿ ಸಂಚರಿಸಿ ಮರಗಳು ಏಕಕಾಲದಲ್ಲಿ. ಮೊದಲ ಮರಕ್ಕಾಗಿ, ಪ್ರಸ್ತುತ ಹಂತದ ಅಂಶ ಮತ್ತು ಆವರ್ತನವನ್ನು a ನಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಮತ್ತು ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್‌ನಲ್ಲಿ ಪ್ರಸ್ತುತ ಅಂಶ ಇಲ್ಲದಿದ್ದರೆ ಎರಡನೇ ಮರದ ಪ್ರಸ್ತುತ ಮಟ್ಟಕ್ಕೆ. ಎಲ್ಲಾ ಹಂತಗಳು ಅನಗ್ರಾಮ್ಗಳಲ್ಲ. ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್‌ನಲ್ಲಿ ಆ ಅಂಶದ ಆವರ್ತನವನ್ನು ಕಡಿಮೆ ಮಾಡಿ. ಅಡ್ಡಹಾಯುವಿಕೆಯ ಕೊನೆಯಲ್ಲಿ, ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಖಾಲಿಯಾಗಿದ್ದರೆ, ಎರಡೂ ಮರಗಳ ಈ ಮಟ್ಟವು ಅನಗ್ರಾಮ್ ಮುಂದಿನ ಹಂತಗಳಿಗೆ ಮುಂದುವರಿಯುತ್ತದೆ, ಇಲ್ಲದಿದ್ದರೆ ಎಲ್ಲಾ ಹಂತಗಳು ಇಲ್ಲ ಅನಗ್ರಾಮ್ಗಳು.

  1. ಎರಡು ರಚಿಸಿ ಬಾಲಗಳು q1 ಮತ್ತು q2, q1 ಅನ್ನು ಮರ 1 ಅನ್ನು ಹಾದುಹೋಗಲು ಬಳಸಲಾಗುತ್ತದೆ ಮತ್ತು q2 ಅನ್ನು q2 ಅನ್ನು ಹಾದುಹೋಗಲು ಬಳಸಲಾಗುತ್ತದೆ.
  2. ಮರದ ಮೂಲವನ್ನು 1 ರಿಂದ q1 ಮತ್ತು ಮರದ ಮೂಲವನ್ನು 2 ರಿಂದ q2 ಗೆ ತಳ್ಳಿರಿ.
  3. Q1 ಖಾಲಿಯಾಗಿಲ್ಲ ಅಥವಾ q2 ಖಾಲಿಯಾಗಿಲ್ಲದಿದ್ದರೂ ಹಂತ 4, 5 ಮತ್ತು 6 ಅನ್ನು ಪುನರಾವರ್ತಿಸಿ.
  4. ಅಂಶಗಳನ್ನು ಮತ್ತು ಪ್ರಸ್ತುತ ಹಂತದ ಅಂಶಗಳ ಆವರ್ತನವನ್ನು ಸಂಗ್ರಹಿಸಲು ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ರಚಿಸಿ. ಒಂದು ಪೂರ್ಣಾಂಕ ಗಾತ್ರ 1 ಅನ್ನು q1 ಗಾತ್ರದಂತೆ ಪ್ರಾರಂಭಿಸಿ. ಗಾತ್ರ 0 ಕ್ಕಿಂತ 1 ರಿಂದ ಕಡಿಮೆ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ. ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ q1 ಕ್ಯೂನಿಂದ ಒಂದು ಅಂಶವನ್ನು ಪಾಪ್ and ಟ್ ಮಾಡಿ ಮತ್ತು ಅದನ್ನು ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್‌ಗೆ ಸೇರಿಸಿ. ಪ್ರಸ್ತುತ ಅಂಶದ ಮಕ್ಕಳನ್ನು ತಳ್ಳಿರಿ ಕ್ಯೂ.
  5. ಪೂರ್ಣಾಂಕ ಗಾತ್ರ 2 ಅನ್ನು q2 ಗಾತ್ರದಂತೆ ಪ್ರಾರಂಭಿಸಿ. ಗಾತ್ರ 0 ಕ್ಕಿಂತ 2 ರಿಂದ ಕಡಿಮೆ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ. ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ, ಕ್ಯೂ q2 ನಿಂದ ಒಂದು ಅಂಶವನ್ನು ಪಾಪ್ out ಟ್ ಮಾಡಿ ಮತ್ತು ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್‌ನಲ್ಲಿ ಈ ಅಂಶ ಇದ್ದರೆ ಅದರ ಆವರ್ತನವನ್ನು 1 ರಷ್ಟು ಕಡಿಮೆ ಮಾಡಿ, ಇಲ್ಲದಿದ್ದರೆ ತಕ್ಷಣವೇ ಸುಳ್ಳನ್ನು ಹಿಂತಿರುಗಿಸಿ.
  6. ಲೂಪ್ನ ಕೊನೆಯಲ್ಲಿ, ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಒಂದು ಅಂಶವನ್ನು ಹೊಂದಿದ್ದರೆ, ಸುಳ್ಳನ್ನು ಹಿಂತಿರುಗಿಸಿ, ಇಲ್ಲದಿದ್ದರೆ ಎರಡು ಮರಗಳ ಈ ಮಟ್ಟವು ಅನಗ್ರಾಮ್‌ಗಳು, ಮುಂದಿನ ಹಂತಕ್ಕೆ ಮುಂದುವರಿಯಿರಿ.
  7. ನಾವು ಇಲ್ಲಿಗೆ ತಲುಪಿದರೆ, ಎರಡು ಮರಗಳ ಎಲ್ಲಾ ಹಂತಗಳು ಅನಗ್ರಾಮ್‌ಗಳಾಗಿವೆ, ಆದ್ದರಿಂದ ನಿಜಕ್ಕೆ ಹಿಂತಿರುಗಿ.

ಕೋಡ್

ಎರಡು ಬೈನರಿ ಮರದ ಎಲ್ಲಾ ಹಂತಗಳು ಅನಗ್ರಾಮ್‌ಗಳೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಲು ಜಾವಾ ಕೋಡ್

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

class CheckIfAllLevelsOfTwoBinaryTreeAreAnagramsOrNot {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

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

    private static boolean checkIsAnagrams(Node tree1, Node tree2) {
        // create two queues
        Queue<Node> q1 = new LinkedList<>();
        Queue<Node> q2 = new LinkedList<>();
        // add root of tree1 to q1
        q1.add(tree1);
        // add root of tree2 to q2
        q2.add(tree2);

        // while either of q1 or q2 is not empty
        while (!q1.isEmpty() || !q2.isEmpty()) {
            // create a hash map to store freq of elements of a level
            HashMap<Integer, Integer> freq = new HashMap<>();

            // traverse this level of tree1
            int size1 = q1.size();
            for (int i = 0; i < size1; i++) {
                // remove a node from queue
                Node curr = q1.poll();
                // add the element to hash map
                if (freq.containsKey(curr.data)) {
                    freq.put(curr.data, freq.get(curr.data) + 1);
                } else {
                    freq.put(curr.data, 1);
                }

                // add curr's children to queue
                if (curr.left != null)
                    q1.add(curr.left);
                if (curr.right != null)
                    q1.add(curr.right);
            }

            // traverse this level of tree2
            int size2 = q2.size();
            for (int i = 0; i < size2; i++) {
                // remove a node from q2
                Node curr = q2.poll();
                // decrease the frequency of this element in hash map
                if (freq.containsKey(curr.data)) {
                    int frequency = freq.get(curr.data);
                    frequency--;
                    if (frequency == 0) {
                        freq.remove(curr.data);
                    } else {
                        freq.put(curr.data, frequency);
                    }
                } else {
                    return false;
                }

                // add curr's children to queue
                if (curr.left != null)
                    q2.add(curr.left);
                if (curr.right != null)
                    q2.add(curr.right);
            }

            // if there is an element in the hash map
            // the two tree's current levels are not anagrams
            if (freq.size() > 0) {
                return false;
            }
        }

        // all the levels are anagrams, return true
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        Node tree1_1 = new Node(5);
        tree1_1.left = new Node(4);
        tree1_1.right = new Node(3);
        tree1_1.left.left = new Node(2);
        tree1_1.left.right = new Node(1);

        Node tree2_1 = new Node(5);
        tree2_1.left = new Node(3);
        tree2_1.right = new Node(4);
        tree2_1.left.left = new Node(1);
        tree2_1.right.left = new Node(2);

        System.out.println(checkIsAnagrams(tree1_1, tree2_1));

        // Example 2
        Node tree1_2 = new Node(5);
        tree1_2.left = new Node(7);
        tree1_2.right = new Node(8);
        tree1_2.left.left = new Node(9);

        Node tree2_2 = new Node(5);
        tree2_2.left = new Node(7);
        tree2_2.right = new Node(8);
        tree2_2.left.left = new Node(1);
        tree2_2.right.left = new Node(2);

        System.out.println(checkIsAnagrams(tree1_2, tree2_2));
    }
}
true
false

ಎರಡು ಬೈನರಿ ಮರದ ಎಲ್ಲಾ ಹಂತಗಳು ಅನಗ್ರಾಮ್‌ಗಳೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಲು ಸಿ ++ ಕೋಡ್

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

// class representing node of a binary tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node with given data
Node* newNode(int data) {
    Node *node = new Node(data);
    return node;
}

bool checkIsAnagrams(Node *tree1, Node *tree2) {
    // create two queues
    queue<Node *> q1;
    queue<Node *> q2;
    // add root of tree1 to q1
    q1.push(tree1);
    // add root of tree2 to q2
    q2.push(tree2);
    
    // while either of q1 or q2 is not empty
    while (!q1.empty() || !q2.empty()) {
        // create a hash map to store freq of elements of a level
        unordered_map<int, int> freq;
        
        // traverse this level of tree1
        int size1 = q1.size();
        for (int i = 0; i < size1; i++) {
            // remove a node from queue
            Node *curr = q1.front();
            q1.pop();
            
            // add the element to hash map
            auto itr = freq.find(curr->data);
            if (itr != freq.end()) {
                itr->second++;
            } else {
                freq.insert(make_pair(curr->data, 1));
            }
            
            // add curr's children to queue
            if (curr->left != NULL)
                q1.push(curr->left);
            if (curr->right != NULL)
                q1.push(curr->right);
        }
        
        // traverse this level of tree2
        int size2 = q2.size();
        for (int i = 0; i < size2; i++) {
            // remove a node from q2
            Node *curr = q2.front();
            q2.pop();
    
            // decrease the frequency of this element in hash map
            auto itr = freq.find(curr->data);
            if (itr != freq.end()) {
                itr->second--;
                if (itr->second == 0) {
                    freq.erase(itr);
                }
            } else {
                return false;
            }
            
            // add curr's children to queue
            if (curr->left != NULL)
                q2.push(curr->left);
            if (curr->right != NULL)
                q2.push(curr->right);
        }
        
        // if there is an element in the hash map
        // the two tree's current levels are not anagrams
        if (freq.size() != 0)
            return false;
    }
    
    // all the levels are anagrams, return true
    return true;
}

int main() {
    // Example 1
    Node *tree1_1 = newNode(5);
    tree1_1->left = newNode(4);
    tree1_1->right = newNode(3);
    tree1_1->left->left = newNode(2);
    tree1_1->left->right = newNode(1);

    Node *tree2_1 = new Node(5);
    tree2_1->left = newNode(3);
    tree2_1->right = newNode(4);
    tree2_1->left->left = newNode(1);
    tree2_1->right->left = newNode(2);

    if (checkIsAnagrams(tree1_1, tree2_1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    Node *tree1_2 = newNode(5);
    tree1_2->left = newNode(7);
    tree1_2->right = newNode(8);
    tree1_2->left->left = newNode(9);

    Node *tree2_2 = newNode(5);
    tree2_2->left = newNode(7);
    tree2_2->right = newNode(8);
    tree2_2->left->left = newNode(1);
    tree2_2->right->left = newNode(2);

    if (checkIsAnagrams(tree1_2, tree2_2)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }   
    
    return 0;
}
true
false

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ನಾವು ಎರಡೂ ಮರಗಳನ್ನು ನಿಖರವಾಗಿ ಒಮ್ಮೆ ಹಾದುಹೋಗುವಾಗ ಮತ್ತು ಲೆವೆಲ್ ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್ಗಾಗಿ ಎರಡು ಸಾಲುಗಳನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ = ಒ (ಎನ್ + ಮೀ)
ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ = ಒ (ಎನ್ + ಮೀ)
ಇಲ್ಲಿ n ಎಂಬುದು ಮರ 1 ರಲ್ಲಿನ ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆ ಮತ್ತು m ಎಂಬುದು ಮರ 2 ರಲ್ಲಿನ ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆ.