algorithm - 检查一棵树是否是镜像？

Question

给定一棵巨大且无法放入内存的二叉树，如何检查该树是否为镜像。

我把这个作为面试问题

Answer 1

如果一棵树是另一棵树的镜像，那么一棵树的中序遍历将与另一棵树相反。

因此，只需对第一棵树进行中序遍历，对另一棵树进行反向中序遍历，然后检查所有元素是否相同。

Answer 2

当然，我不能完全相信这个答复。我的一些同事帮助提出了一些假设，并在我最初的想法中戳了洞。非常感谢他们！

假设

• 我们不能将整个树都放在内存中，因此使用递归并不理想。为简单起见，假设我们在内存中最多只能保存两个节点。

• 我们知道n，我们树中的总层数。

• 我们可以根据数据所在的字符或行位置对数据执行搜索。

• 磁盘上的数据按深度排序。也就是说，磁盘上的第一个条目是根，接下来的两个是它的孩子，接下来的四个是它的孩子的孩子，依此类推。

• 在某些情况下，数据是完全镜像的，在某些情况下则不是。除非另有说明，与非空白数据交错的空白数据被认为是“可接受的”。

• 只要可以比较值是否相等，我们就可以自由使用我们希望的任何数据类型。对象等效性测试可能并不理想，因此假设我们正在比较原语。

• “镜像”意味着在根的孩子之间镜像。使用不同的术语，祖父母的左孩子与其右孩子镜像，左孩子（父母）的左孩子与祖父母的右孩子的右孩子镜像。如下图所示；匹配的符号代表我们要检查的镜像。

              G
        P*         P*
     C1&  C2^   C3^ C4&
  

方法

我们知道当我们从磁盘读取时，我们应该期望每个级别上有多少个节点 - 2 ^k的一些倍数。我们可以建立一个双循环来迭代树的总深度，以及每个级别的节点数。在这里面，我们可以简单地比较最外层的值是否相等，如果发现不相等的值则短路。

^{我们可以使用 2 k}的倍数来确定每个外部位置的位置。任何级别的最左边的孩子总是 2 ^k，任何级别的最右边的孩子总是 2 ^k+1 -1。

小证明：1 层最外层节点为 2 和 3；2 ¹ = 2, 2 ¹⁺¹ -1 = 2 ² -1 = 3。第 2 层最外层的节点是 4 和 7；2 ² = 4, 2 ²⁺¹ -1 = 2 ³ -1 = 7。可以将其一直扩展到第 n 种情况。

伪代码

int k, i;
for(k = 1; k < n; k++) { // Skip root, trivially mirrored
    for(i = 0; i < pow(2, k) / 2; i++) {
        if(node_retrieve(i + pow(2, k)) != node_retrieve(pow(2, (k+1)-i)) {
            return false;
        }
     }
 }
 return true;

想法

这类问题是一个很好的面试问题，因为他们很可能想看看你将如何解决这个问题。这种方法可能很糟糕，也可能完美无瑕，但雇主会希望你慢慢来，在一张纸或白板上画一些东西，并向他们询问有关如何存储数据、如何读取数据、什么是数据的问题搜索等方面存在限制。

面试官感兴趣的不是编码方面，而是解决问题方面。

Answer 3

递归很容易。

struct node {
        struct node *left;
        struct node *right;
        int payload;
        };

int is_not_mirror(struct node *one, struct node *two)
{
if (!one && !two) return 0;
if (!one) return 1;
if (!two) return 1;
if (compare(one->payload, two->payload)) return 1;
if (is_not_mirror(one->left, two->right)) return 1;
if (is_not_mirror(one->right, two->left)) return 1;
return 0;
}