二叉树学习

//已知中序遍历和后序遍历输出前序遍历
//每次输出根节点就好

#include <bits/stdc++.h>
using namespace std;

void solve(string in,string post)
{
    int l=in.length();
    if(l>0)
    {
        cout<<post[l-1];//根节点
        int k=in.find(post[l-1]);
        solve(in.substr(0,k),post.substr(0,k));//左子树 
        solve(in.substr(k+1),post.substr(k,l-k-1));//右子树 
    }
    else 
        return ;    
}

int main()
{
    string inorder,postorder;
    cin>>inorder>>postorder;
    solve(inorder,postorder);
    return 0;
}
//find返回的是数组的下标 

//已知前序遍历和中序遍历输出后续遍历
//到递归返回时输出前序遍历的首位

#include <bits/stdc++.h>
using namespace std;

void solve(string pre,string in)
{
    int l=in.length();
    if(l>0)
    {
        int k=in.find(pre[0]);
        solve(pre.substr(1,k),in.substr(0,k));
        solve(pre.substr(k+1,l-k-1),in.substr(k+1));
        cout<<pre[0];
    }
    else 
        return ;    
}

int main()
{
    string preorder,inorder;
    cin>>preorder>>inorder;
    solve(preorder,inorder);
    return 0;
}