18724 二叉树的遍历运算

先序遍历的顺序是 根左右 ；中序遍历的顺序是 左根右

l1表示先序遍历的左边界，r1表示先序遍历的右边界
l2表示中序遍历的左边界，r1表示中序遍历的右边界
下面以题目的输入样例为例做分析

输入样例
abcde
bcade

当i到达最后落点时，中序遍历中的左右子树被i分割

图一：

有图一可以知道：

1. 从中序遍历可以知道左子树长度（i-l2）
2. 右子树为（r2-i）

利用递归算法求左右子树（如图二）

#include <iostream>
#include <string>
using namespace std;
string s1,s2;
void solve(int l1,int r1,int l2,int r2){
       char c=s1[l1];
   
       if(l1>r1||l2>r2)return;
       int i;
       for(i=l2;i<=r2;i++){
        if(c==s2[i])break;
       }
       solve(l1+1,r1-(r2-i),l2,i-1);
       solve(r1-(r2-i-1),r1,i+1,r2);
       cout<<c;//输出根节点
}
int main()
{
    cin>>s1>>s2;
    int len1=s1.size();
    int len2=s2.size();
    solve(0,len1-1,0,len2-1);
    return 0;
}

c++中，在获取字符串长度时，size()函数与length()函数作用相同。