云服务器

商务合作:179001057@qq.com

1210. 二叉树

xiaoxiao2021-09-20  26


某平台价值19860元的编程课程资料免费领取【点我领取】


对一棵二叉树,如果给出前序遍历和中许遍历的结点访问顺序,那么后序遍历的顺序是唯一确定的,也很方便地求出来。但如果现在只知道前序遍历和后序遍历的顺序,中序遍历的顺序是不确定的,例如:前序遍历的顺序是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; }