如何区分中序遍历相同但结构不同的两棵BST？

先看你给出的这些结构不同但元素相同的BST示例（它们的中序遍历都是对应元素的升序结果）：

第一个链状结构：

1 
 \ 
  2 
   \ 
    3 
     \ 
      4

另一个分支结构：

2 
 / \ 
1   3 
     \ 
      4

还有这类交叉结构：

4 
   / 
  1 
   \ 
    2 
     \ 
      3

这些树的中序遍历结果完全一致，但结构天差地别。要区分它们，以及判断不同插入序列是否生成同一结构，我们可以从这几个实用方法入手：

一、用带空节点标记的序列化来唯一标识BST结构 #

BST的结构差异核心是节点的层级关系和左右子树的分布，单独的前序/后序遍历可能会有歧义，但如果我们在序列化时加入空节点的标记（比如用#表示），就能生成唯一的结构字符串：

比如第一个链状树的前序序列化（带空标记）是：1,#,2,#,3,#,4,#,#
第二个分支树的前序序列化是：2,1,#,#,3,#,4,#,#
第三个树的前序序列化是：4,1,#,2,#,3,#,#,#

通过对比这些序列化字符串，就能直接判断两个BST的结构是否不同。你也可以用层次遍历（BFS）序列化，同样带上空节点标记，比如第一个树的层次序列化是1,#,2,#,3,#,4，第二个是2,1,3,#,#,#,4，效果一样。

二、判断不同插入序列是否生成同一BST #

你提到的例子：序列2,1,4,5、2,4,1,3、2,4,3,1，要判断它们是否生成同一结构，有两种简单方法：

• 模拟插入法：分别用每个序列一步步构建BST，然后对比它们的序列化结果（用上面的带空标记方法），如果序列化字符串完全一致，说明结构相同。这种方法直观，适合大多数场景。
• 规则推导法：利用BST的插入规则——每个新节点从根出发，比当前节点小就往左走，大就往右走。如果两个序列生成同一结构，那么对于每个节点来说，它的左子树节点集合和右子树节点集合的插入顺序要满足约束：比如根节点是2，所有比2小的节点（比如1）必须都插入到左子树，比2大的（4,3,5）插入到右子树；右子树的根是4，比4小的3要插入到它的左子树，大的5插入到右子树。只要两个序列中，每个节点的“相对插入优先级”符合这个逻辑，最终结构就会一致。

为什么中序遍历搞不定？ #

因为BST的中序遍历天然就是节点的升序排列——不管树的结构怎么变，只要元素集合相同，中序结果肯定是一样的。它只能反映节点的大小顺序，完全体现不出树的层级、左右子树的分布，所以必须结合其他遍历信息或者序列化方式才能区分结构。

内容的提问来源于stack exchange，提问作者Gaurav