두 이진 트리의 모든 수준이 애너그램인지 확인

난이도 하드
자주 묻는 질문 어도비 벽돌 아마존 Facebook 광신자 포카이트 그레이 오렌지
철자 바꾸기 이진 트리 나무조회수 31

문제 정책

"두 이진 트리의 모든 레벨이 애너그램인지 확인하십시오"라는 문제는 두 이진 트리가 주어 졌는지, 두 트리의 모든 레벨이 애너그램인지 확인한다고 말합니다.

입력

두 이진 트리의 모든 수준이 애너그램인지 확인

true

입력

두 이진 트리의 모든 수준이 애너그램인지 확인

false

두 바이너리 트리의 모든 수준이 애너그램인지 확인하는 알고리즘

우리는 해싱 이 문제를 해결하기 위해. XNUMX 단계마다 이동 나무 동시에. 첫 번째 트리의 경우 현재 레벨의 요소와 빈도를 해시맵 두 번째 트리의 현재 레벨에 대해 현재 요소가 HashMap에없는 경우. 모든 레벨은 철자가 아닙니다. 그렇지 않으면 HashMap에서 해당 요소의 빈도를 줄입니다. 순회가 끝날 때 HashMap이 비어있는 경우 두 트리의이 수준은 다음 수준에 대한 애너그램 계속됩니다. 그렇지 않으면 모든 수준이 그렇지 않습니다. 아나 그램.

  1. 두 개 만들기 꼬리 q1 및 q2, q1은 트리 1을 횡단하는 데 사용되고 q2는 q2를 횡단하는 데 사용됩니다.
  2. 나무 1의 뿌리를 q1로, 나무 2의 뿌리를 q2로 밉니다.
  3. q1이 비어 있지 않거나 q2가 비어 있지 않은 동안 4, 5, 6 단계를 반복합니다.
  4. 현재 레벨 요소의 요소와 빈도를 저장하는 HashMap을 작성하십시오. 정수 size1을 q1의 크기로 초기화합니다. 0에서 size1 미만까지 루프를 실행합니다. 반복 할 때마다 큐 q1에서 요소를 꺼내서 HashMap에 추가합니다. 현재 요소의 자식을 변발.
  5. 정수 size2를 q2의 크기로 초기화합니다. 0에서 size2 미만까지 루프를 실행합니다. 반복 할 때마다 큐 q2에서 요소를 팝하고이 요소가 HashMap에 있으면 빈도를 1만큼 줄이고 그렇지 않으면 즉시 false를 반환합니다.
  6. 루프의 끝에서 HashMap에 요소가 포함되어 있으면 false를 반환합니다. 그렇지 않으면 두 트리의이 수준이 아나그램이고 다음 수준으로 계속됩니다.
  7. 여기에 도달하면 두 트리의 모든 수준이 아나그램이므로 true를 반환합니다.

암호

두 바이너리 트리의 모든 레벨이 애너그램인지 확인하는 자바 코드

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

두 이진 트리의 모든 수준이 애너그램인지 확인하는 C ++ 코드

#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

복잡성 분석

두 트리를 정확히 한 번 순회하고 레벨 순서 순회에 두 개의 큐를 사용 했으므로

시간 복잡성 = O (n + m)
공간 복잡성 = O (n + m)
여기서 n은 트리 1의 노드 수이고 m은 트리 2의 노드 수입니다.

Translate »