data-structures - 堆栈图是否需要 n 个正方形空间？

Question

我正在研究这个geeksforgeeks 问题：

检查 N 叉树中的镜像

给定两个n叉树。检查它们是否是彼此的镜像。您还得到e表示两棵树中的边数，以及两个数组A[]和B[]。每个数组都有 2*e 空格分隔值 u,v 表示两棵树的从 u 到 v 的边。

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

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

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

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

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

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

标签： data-structurestreestlbinary-treespace-complexity

Answer 1

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

堆栈映射是否不需要 n 平方空间，因为每个索引都将使用 O(n) 大小的堆栈？

不，即使一个堆栈的大小可能为 O()，但一个如此大的堆栈会限制其他堆栈的大小。一棵树有 O() 条边——实际上，正好是 -1 条边——所以堆栈大小的总和仍然是 O()，因此对于map 和堆栈的 O()，相当于 O()。