NOJ 1848--二叉树
(3)? 如果PreStr[1]!= PostStr[Length-2],显然存在左右子树(PostStr中以与PreStr[1]相等的位置分为左右子树)，对左右子树分别作为一颗独立的子树进行处理
?
#include <stdio.h>#include <string.h>char PreStr[30]; //前序遍历的字符串char PostStr[30]; //后序遍历的字符串int count; //记录只有一个子树的节点的个数void calc(int a1,int b1,int a2,int b2){ /*计算前序遍历a1到b1的子串,后序遍历a2到b2的子串*/ int i; if(a1>=b1) return; //子串长度为1时不需要作出处理 for(i=a2; i<=b2-1; i++) //寻找左子树的位置 { if(PreStr[a1+1] == PostStr[i]) break; } if(i == b2-1) count++; //只有一颗子树时 calc(a1+1,a1+1+(i-a2),a2,i); //处理左子树 calc(a1+1+(i-a2)+1,b1,i+1,b2-1); //处理右子树}int Pow(int n){ /*计算2的n次方*/ int i; int m = 1; for(i = 0; i < n; i++) { m *= 2; } return m;}int main(){ int Length; scanf("%s", PreStr); scanf("%s", PostStr); Length = strlen(PreStr); count = 0; calc(0,Length-1,0,Length-1); printf("%d\n", Pow(count)); return 0;}?