[数据结构与算法] 树的中序遍历+前序遍历得到后序遍历

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 树的中序遍历+前序遍历得到后序遍历 -> 正文阅读

[数据结构与算法]树的中序遍历+前序遍历得到后序遍历

P1827 [USACO3.4] 美国血统 American Heritage
在这里插入图片描述

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

string in, pre;

string dfs(int idx, int l, int r)
{
	//递归结束条件 
	if(l > r) return "";
	
	//找到以idx为根的中序遍历下标，然后将中序遍历分割成左右子树 
	int i = l;
	while(i < r && in[i] != pre[idx]) i ++;
	
	string post = "";
	//左子树根节点idx + 1，l, i - 1中序遍历端点 
	post += dfs(idx + 1, l, i - 1);
	//右子树根节点为idx + i - l + 1, i + 1, r 中序遍历端点 
	post += dfs(idx + (i - l) + 1, i + 1, r);
	//将根节点加入字符串，相当于树的后续遍历架构 
	post += pre[idx];
	
	return post;
}

int main()
{
	cin >> in >> pre;
	
	//根节点在前序中的下标，中序序列的左右端点 
	cout << dfs(0, 0, in.size() - 1) << endl;
	
	return 0;
}