composer 檢查鏡像

Problem statement:

問題陳述：

Given two n-ary trees, the task is to check if they are mirrors of each other or not.

給定兩個n元樹，任務是檢查它們是否互為鏡像。

Note: you may assume that root of both the given tree as 1.

注意：您可以假設兩個給定樹的根均為1。

Input:

輸入：

The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two space-separated values N and M denoting the no. of nodes and edges respectively. Then in the next line, two lines are 2*M space-separated values u, v denoting an edge from u to v for both trees.

輸入的第一行包含一個整數T，表示測試用例的數量。 然后是T測試用例。 每個測試用例的第一行包含兩個以空格分隔的值N和M，表示編號。 分別為節點和邊。 然后在下一行中，兩行是2 * M個空格分隔的值u ， v表示兩棵樹從u到v的邊。

Output:

輸出：

For each test case in a new line print "YES" if both the trees are mirrors of each other else print "NO".

對于新行中的每個測試用例，如果兩棵樹都是彼此的鏡像，則打印“是”，否則打印“否”。

Examples:

例子：

INPUT:	
T=1
N=3,M=3
1 2 1 3 2 4
1 3 1 2 2 4
OUTPUT: 
YES
1                  1
/ \                / \
2   3              3   2
/                        \
4                         4
Since they are mirror of each other.
INPUT:
T=1
N=4,M=4
1 2 1 3 2 4 2 5
1 3 1 2 2 4 2 5
OUTPUT: 
NO
1                     1
/ \                   / \
2   3                 3   2
/ \                       / \
4   5                     4   5
Here, 
node 4 and 5 are not as in mirror so the tree is not mirror.

Solution Approach

解決方法

We will use stack and queue data structure since stack follow LIFO that is last in first out the way and queue follow FIFO first in first out pattern, is the trees are mirror then the top of the stack will be equal to the front of the queue and if they aren't equal it means that they are not the mirror of each other.

我們將使用堆棧和隊列數據結構，因為堆棧遵循后進先出的方式，而隊列遵循先進先出的先入先出模式，因為樹是鏡像的，因此堆棧的頂部等于隊列的前端如果它們不相等，則意味著它們不是彼此的鏡像。

We will follow this approach, taking each node at a time and checking its connected component in stack and queue. For checking whether each subtree in itself is a mirror or not we will use a boolean variable flag, initially, the flag is true and each time we check if the top of stack and queue front are equal or not, if not then simply return NO as the answer and after checking all nodes return true if all are valid nodes.

我們將采用這種方法，一次獲取每個節點，并在堆棧和隊列中檢查其連接的組件。 為了檢查每個子樹本身是否是鏡像，我們將使用布爾變量標志，該標志最初為true，并且每次我們檢查棧頂和隊列前部是否相等時(如果不相等)，則簡單地返回NO作為答案，并且在檢查所有節點后，如果所有節點都是有效節點，則返回true。

C++ Implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll t;
cout << "Enter number of test cases: ";
cin >> t;
while (t--) {
ll n, m;
cout << "Enter number of nodes and edges: ";
cin >> n >> m;
// declare a vector of stacks of size (n+1)
// since index start from 0.
stack<int> v1[n + 1];
// declare a vector of queue of size (n+1)
// since index start from 0.
queue<int> v2[n + 1];
cout << "Enter tree 1: ";
for (ll i = 0; i < m; i++) {
ll x, y; //enter the elements of its.
cin >> x >> y;
v1[x].push(y);
}
cout << "Enter tree 2: ";
for (ll i = 0; i < m; i++) {
ll x, y;
cin >> x >> y; //enter elements of tree 2.
v2[x].push(y);
}
bool flag;
// iterate through each node.
for (int i = 1; i <= n; i++) {
// store nodes of tree 1 connected components in stack
stack<int>& s = v1[i];
// store nodes of tree 1 connected components in queue
queue<int>& q = v2[i];
// declare a boolean variable to check mirror
// property among the elements.
flag = true;
//compare the stack top to queue top.
while (!s.empty() and !q.empty()) {
// if not similar then break from the loop.
if (s.top() != q.front()) {
flag = false;
break;
}
s.pop();
q.pop();
}
// if not similar then break from the nodes loop
// since no further comparison is needed.
if (flag == false)
break;
}
// check if mirror or not.
cout << "Is Mirror: ";
if (flag == true)
cout << "YES"
<< "\n";
else
cout << "NO"
<< "\n";
}
return 0;
}

Output:

輸出：

Enter number of test cases: 3
Enter number of nodes and edges: 4 4 
Enter tree 1: 1 2 1 3 2 4 2 5
Enter tree 2: 1 2 1 3 2 5 2 4
Is Mirror: NO
Enter number of nodes and edges: 3 2
Enter tree 1: 1 2 1 3
Enter tree 2: 1 3 1 2
Is Mirror: YES
Enter number of nodes and edges: 3 3
Enter tree 1: 1 2 1 3 2 4
Enter tree 2: 1 3 1 2 2 4
Is Mirror: YES

• The time complexity for the above approach in worst case: O(n*n)

  最壞情況下上述方法的時間復雜度： O(n * n)

• Space complexity for the above approach in worst case : O(n)

  上述方法在最壞情況下的空間復雜度： O(n)

---

---

Also tagged in: Amazon, DE-Shaw, Hike, MakeMyTrip

也標記在： 亞馬遜 ， DE-Shaw ， 遠足 ， MakeMyTrip

Problem source: https://practice.geeksforgeeks.org/problems/check-mirror-in-n-ary-tree/0

問題來源：https：//practice.geeksforgeeks.org/problems/check-mirror-in-n-ary-tree/0

翻譯自: https://www.includehelp.com/icp/check-mirror-in-n-ary-tree.aspx

composer 檢查鏡像