本文主要是介绍1086. Tree Traversals Again (25)[递归＋二叉树]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 原题： https://www.patest.cn/contests/pat-a-practise/1086
2. 思路：
递归＋二叉树的遍历问题
题意：
用栈模拟树的遍历，输出后序
思路：
入栈序列其实是二叉树的前序，出栈序列是中序。
所以，问题就是利用前序和中序输出后序。
显然，用递归处理啦。
已ＡＣ
题意：
用栈模拟树的遍历，输出后序
思路：
入栈序列其实是二叉树的前序，出栈序列是中序。
所以，问题就是利用前序和中序输出后序。
显然，用递归处理啦。
已ＡＣ
3. 源码：
#include<iostream>
#include<vector>
#include<stack>
#include<string>
using namespace std;int N;//结点数
vector<int> ino, pre;//分别存储中序和前序的序列
int findPos(int x);//找出前序中的第x个元素在中序的位置
void post(int left, int right, int ro_pos);//输出后序, 参数分别是中序的左、右边界，前序的根位置int main(void)
{//freopen("in.txt", "r", stdin);cin >> N;stack<int> sta;//栈for (int i = 0; i < 2 * N; i++)//读入数据{string s;int data;cin >> s;if (s[1] == 'u')//构建前序序列{cin >> data;sta.push(data);pre.push_back(data);}else//构建中序序列{data = sta.top();sta.pop();ino.push_back(data);}}post(0, N - 1, 0);//递归输出后序return 0;
}int findPos(int x)//找出前序中的第x个元素在中序的位置
{int i;for (i = 0; i < N; i++){if (ino[i] == pre[x])break;}return i;
}void post(int left, int right, int ro_pos)//参数分别是中序的左、右边界，前序的根位置
{if (left > right)//递归终止条件return;int ino_pos = findPos(ro_pos);post(left, ino_pos - 1, ro_pos + 1);//递归左子树post(ino_pos + 1, right, (ro_pos + ino_pos - left + 1));//递归右子树if (ro_pos == 0)//输出根结点cout << pre[ro_pos] << endl;elsecout << pre[ro_pos] << ' ';
}这篇关于1086. Tree Traversals Again (25)[递归＋二叉树]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
