algorithm - 给定两棵完全二叉树的层序遍历，如何判断一棵树是否是另一棵树的镜像？

Question

如何在只给出树的层序遍历的情况下判断两棵完全二叉树是否互为镜像？

完全二叉树是一棵除叶节点外的所有节点都有2个子节点的二叉树。

Answer 1

我认为这是不可能的。考虑这两棵树:

   0              0
  / \          /     \
 1   2        1       2
    / \      / \     / \
   3   4    3   4   5   6
  / \
 5   6

这些是完整的二叉树(根据您的定义)，尽管它们是不同的树，但它们具有相同的层序遍历:0123456。

现在，看看他们的镜子:

    0              0
   / \          /     \
  2   1        2       1
 / \          / \     / \
4   3        6   5   4   3
   / \
  6   5

注意左边树的层序遍历为0214365，而右边树的层序遍历为0216543。也就是说，原始树的层序遍历相同，但它们的镜像树的遍历不同。

现在，想想如果您有自己的算法并输入 0123456(任一树的层序遍历)和 0214365(其中一个镜像的层序遍历)会发生什么。算法能说什么？如果它说它们是镜像，那么如果您输入第二个输入树，那将是错误的。如果它说它们不是镜像，那么如果您输入第一个输入树，那将是错误的。因此，算法无法始终产生正确答案。

希望这对您有所帮助!