题解 P1827 【美国血统 American Heritage】

jzqjzq · 2017-02-01 11:28:24 · 题解

来一发C++递归。

自然，根据中序遍历和前序遍历，在子树区间中找到根的方法是。。。

其实前序遍历本区间第一个就是该子树的根（这个应该都知道）

然后就在中序遍历此区间中找到该节点，节点左边就是左子树，右边就是右子树，这样就可以递归了

根据后序遍历性质，输出答案按照以下次序：

-找到节点后：

1.递归左子树

2.递归右子树

3.输出该节点

即为本树的后序遍历。

详见代码：

#include<iostream>
#include<cmath>
#include<string>
#include<cstdio>
using namespace std;
string a,b;
void dfs(int l1,int l2,int l3,int l4){
    if(l1>l2||l3>l4)return;
    for(int i=l1;i<=l2;i++)if(a[i]==b[l3]){//找节点
        dfs(l1,i-1,l3+1,l3+i-l1);//递归左子树
        dfs(i+1,l2,l3+i-l1+1,l4);//递归右子树
        cout<<a[i];//输出该节点
    }
}
int main()
{
    cin>>a>>b;
    int l=a.size();
    dfs(0,l-1,0,l-1);//全树区间
    return 0;
}
这样就华丽丽地结束了，代码比建树短几乎一半，时间可能还快一点