我正在研究这个极客对极客的问题：
检查N元树中的镜像
给定两个nary树。检查它们是否是彼此的镜像。您还得到了表示两个树中边数的e，以及两个数组A[]和B[]。每个数组具有2*e个空间分隔值u，v，表示两个树从u到v的边。
因此，给定的参数是表示两个树的节点之间的边的两个数组(arr1[0]具有与arr1[1]的边，arr1[2]具有与arr1[3]的边，依此类推)。
我使用两个二维向量来完成这项工作，只需将两棵树的边推到它们的节点上，然后反转一棵树的所有边，最后检查两棵树现在的所有边是否相同。
这是一个正确的答案，但所需的最佳解决方案应该是使用O(n)空间，而我使用2-D阵列显然违反了这一点。(n=节点数)
他们的解决方案使用了一个定义为map<int,stack<int>> m的映射，然后使用了与我使用的类似的方法。
我的问题是，它真的是O(n)空间解吗？堆栈映射不需要n2空间吗？因为每个索引都将使用O(n)大小的堆栈？
此外，任何关于任何其他最佳解决方案的提示(关于空间，我希望自己找到及时的最佳解决方案)都将不胜感激。
首先：提到了ary树和节点。为了避免混淆，让我们换个说法吧。但老实说，我认为(关于GfG的)最初的问题不应该说"-ary trees"；(这告诉了一些关于分支因子的内容，参见维基百科)；具有节点的树"；。
堆栈映射是否不需要n平方空间，因为每个索引都将使用O(n)大小的堆栈？
否，即使一个堆栈可以具有O()大小，一个如此大的堆栈也会限制其他堆栈的大小。一棵树有O()条边——实际上，正好是−1条边——所以堆栈大小的和仍然是O()，所以总内存使用量对于映射中的键/引用对是O(。
我认为你是对的。基于map<int,stack<int>> m的解可以达到O(n2)空间。我认为不可能在少于这个空间的情况下完成，因为假设要比较级别k，您需要存储其中的所有节点，以检查它们是否按相反的顺序排列。考虑到root = level 1，任何级别的k > =2都将具有多于n的节点。就时间复杂性而言，我认为我有一个更好的解决方案，它不使用任何映射，因为映射插入或搜索需要O(logn)时间。
using pii = pair<int, int>;
int checkMirrorTree(int n, int e, vi A, vi B) {
if(e==0)return true;
if(A[0]!=B[0])return false;
queue<int> q;
q.push(A[0]);
int i = 0;
while(i<(2*e) && !q.empty()){
int c = q.size();
vector<pii> arr, arr1;
w(i, c);ce
while(c--){
int root = q.front();
q.pop();
while(i<(2*e) && A[i]==root){
q.push(A[i+1]);
arr.push_back({A[i], A[i+1]});
arr1.push_back({B[i], B[i+1]});
i+=2;
}
}
w(i, c);ce
int j=0;int k = arr.size()-1;
w(k, j);ce
w(arr, arr1);ce
while(j<=k){
if(arr[j]!=arr1[k])return false;
j++;
k--;
}
}
return true;
}