堆栈图是否需要 n 平方 space？

Question

Check Mirror in N-ary tree

Given two n-ary trees. Check if they are mirror images of each other or not. You are also given e denoting the number of edges in both trees, and two arrays, A[] and B[]. Each array has 2*e space separated values u,v denoting an edge from u to v for the both trees.

所以给定的参数是两个数组，表示两棵树的节点之间的边（arr1[0] 有一个边 arr1[1] 和 arr1[2] 有一个边 arr1[3]等等）。

我使用两个 2-D 向量来做到这一点，方法是将两棵树的边推到它们的节点上，然后反转一棵树的所有边，最后检查现在两棵树的所有边是否相同。

这是一个正确的答案，但所需的最佳解决方案应该是使用 O(n) space，我显然违反了使用二维数组的要求。（n=节点数）

他们的解决方案使用定义为 map<int,stack<int>> m 的地图，然后使用与我使用的类似的方法。

我的问题是，它真的是 O(n) space 的解决方案吗？堆栈映射不需要 n² space 因为每个索引都将使用 O(n) 大小的堆栈？

此外，任何关于任何其他最佳解决方案的提示（关于 space，我希望自己找到及时的最佳解决方案）将不胜感激。

Answer 1

我认为你是对的。基于 map<int,stack<int>> m 的解决方案总计为 O(n²) space。而且我认为不可能用少于 space 的数量来做到这一点，因为让我们说比较级别 k，你需要存储所有的节点来检查它们是否反向订购与否。任何级别 k > =2，考虑到 root = level 1 都会有超过 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;
}

Answer 2

首先在定义上有一些歧义：提到了 -ary 树和节点。为了避免混淆，让我们来谈谈 -ary 树。但老实说，我认为最初的问题（在 GfG 上）不应该说“-ary 树”（它说明了分支因子，参见 Wikipedia），而是“有节点的树”。

Does map of stacks do not require n squared space as every index will be using a stack of O(n) size ?

不，即使一个堆栈可以有 O() 大小，一个如此大的堆栈限制了其他堆栈的大小。一棵树有 O() 条边——实际上，正好是 −1 条边——所以堆栈大小的 sum 仍然是 O()，所以总内存使用量是 O () 用于映射中的 key/reference 对，O() 用于堆栈，总计 O().

堆栈图是否需要 n 平方 space？

Does map of stacks require n square space?

data-structures

tree

stl

binary-tree

space-complexity

Check Mirror in N-ary tree