由先序和后序遍历求解符合条件的n叉树个数的方法及程序实现福建省晋江市养正中学 张昱峥我们都了解二叉树的先序遍历、中序遍历和后序遍历，当知道先序遍历和中序遍历的结果时，可以唯一的确定二叉树;同样的，当知道后序遍历和中序的结果时，也可以唯一的确定二叉树。但是如果只知道先序遍历和后序遍历的结果时，二叉树就不是唯一的了，但是我们可以计算满足条件的不同二叉树的个数。同样，我们可以将问题推广到N叉树。下面我们以例题进行分析。例一：已知二叉树的先序遍历为：abc，后序遍历为：cba，求满足条件的二叉树的个数。分析：首先容易得出二叉树的根结点一定是a，再由剩下的先序遍历结点序列bc（第一个结点为b）和后序遍历结点序列cb（最后一个结点为b），可知结点bc共同组成根结点a的一个子树，且其中结点b一定是该子树的根结点。这个子树可以是根结点a的左子树，也可以是右子树。如下图所示： ab cab c所以，满足条件的二叉树的个数sum至少为2（sum=2）。又因为对于结点bc来说，c不管是其左结点还是右结点，都满足先序和后序遍历的要求。因此满足条件的二叉树的
