对一棵二叉树，如果给出前序遍历和中许遍历的结点访问顺序，那么后序遍历的顺序是唯一确定的，也很方便地求出来。但如果现在只知道前序遍历和后序遍历的顺序，中序遍历的顺序是不确定的，例如：前序遍历的顺序是ABCD，而后序遍历的顺序是CBDA，那么就有两课二叉树满足这样的顺序。
现在的问题是给定前序遍历和后序遍历的顺序，要求出总共有多少棵不同形态的二叉树满足这样的遍历顺序。
思路：假如根为A的树只有一个子节点B，那么前序和后序为AB和BA（和A相邻的节点相同），此时子节点有左右两种情况；如果A有两个子节点B和C（左B右C），那么前序和后序分别为ABC和BCA，和A相邻的节点不同。
所以，就要求出有单子节点的节点个数single，答案为2的single次方
#include <iostream> #include <string> #include <cmath> using namespace std; int main() { string preorder, postorder; cin>>preorder>>postorder; int single = 0; for ( int i=0; i<preorder.length()-1; i++ ) { for ( int j=postorder.length()-1; j>0; j-- ) { if ( preorder[i] == postorder[j] && preorder[i+1] == postorder[j-1] ) { single++; break; } } } cout<<(int)pow(2.0, (double)single); //pow的参数要用double!!! return 0; }
