algorithm - 是否每层序遍历都唯一定义一个BST？

Question

假设我必须比较两个二叉搜索树是否相似。现在，基本方法是递归公式，检查根是否相等，然后继续检查相应的右子树和左子树是否相等。

但是，如果二叉搜索树具有相同的层序遍历则它们是相同的，这样的说法是否正确？换句话说，是否每个 BST 都有唯一的层序遍历？

Answer 1

不，不是。

第一个:

1
 \
  \
   2
    \
     \
      3

第二个:

   1
  / \
 /   \
2     3

这两个级别的顺序将为 1 - 2 - 3。

由于表示具有 n 个节点的二叉树的信息论下界是 2n - THETA(log n)，我认为任何简单的遍历都不能识别二叉树。

Google 搜索确认下限:

lower bound bits binary tree

从 BST 到二叉树有一个简单的归约。考虑节点值为 1..n 的 BST。这些 BST 的数量是具有 n 个节点的二叉树的数量(您总是可以进行预序遍历并按该顺序插入值)。如果可以使用层序遍历来识别这样的 BST，则可以将 1 用于“层内”节点，将 0 用于“端层”节点。第一棵树变成“000”，第二棵树变成“010”。这将使一个 BST 只被识别为 n 位，不符合信息论下界。