（9 分）对于一个堆栈，若其入栈序列为 $1,2,3,\cdots ,n$ ，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为 $n$ 的二叉树的个数，且与不同形态的二叉树一一对应。请简要论述一种从堆栈输入（固定为 $1,2,3,\cdots ,n$ ）输出序列对应一种二叉树形态的方法，并以入栈序列 $1,2,3$ （即 $n=3$ ）为例加以说明。

入栈出栈序列

[tag_link]

**【答案】** 将固定入栈序列 $1,2,3,\cdots ,n$ 视为二叉树的前序遍历序列，而将出栈序列视为同一二叉树的中序遍历序列。由于二叉树的前序遍历和中序遍历可以唯一确定二叉树的结构，因此每个合法的出栈序列对应一种二叉树形态。

**【解析】** 对于入栈序列 $1,2,\cdots ,n$ ，其出栈序列的个数等于结点个数为 $n$ 的二叉树的个数，即第 $n$ 个卡特兰数。这一一对应可通过二叉树遍历序列建立：入栈序列固定为前序遍历序列，出栈序列作为中序遍历序列。具体地，前序遍历序列确定了根结点的访问顺序，中序遍历序列确定了左子树和右子树的划分，从而唯一重建二叉树。

以 $n=3$ 为例，入栈序列为 $1,2,3$ ，作为前序遍历序列。合法的出栈序列有 $5$ 种，分别作为中序遍历序列，重建二叉树如下：

• 出栈序列 $1,2,3$ ：前序 $1,2,3$ ，中序 $1,2,3$ ，重建得二叉树为根结点 $1$ 的右孩子为 $2$ ， $2$ 的右孩子为 $3$ 。
• 出栈序列 $1,3,2$ ：前序 $1,2,3$ ，中序 $1,3,2$ ，重建得根结点 $1$ 的右孩子为 $2$ ， $2$ 的左孩子为 $3$ 。
• 出栈序列 $2,1,3$ ：前序 $1,2,3$ ，中序 $2,1,3$ ，重建得根结点 $1$ 的左孩子为 $2$ ，右孩子为 $3$ 。
• 出栈序列 $2,3,1$ ：前序 $1,2,3$ ，中序 $2,3,1$ ，重建得根结点 $1$ 的左孩子为 $2$ ， $2$ 的右孩子为 $3$ 。
• 出栈序列 $3,2,1$ ：前序 $1,2,3$ ，中序 $3,2,1$ ，重建得根结点 $1$ 的左孩子为 $2$ ， $2$ 的左孩子为 $3$ 。

这五种二叉树形态恰好对应所有合法的出栈序列，验证了一一对应关系。