By Zhang, Cheng

更新日期:

文章目录
  1. 1. #1049 后序遍历

#1049 后序遍历

这道题目就是给的中序和前序，求字符串的后序输出。

我是用递归来实现的。

中序的第一个字符肯定是根节点，那么在前序中找到该字符的位置，然后前序根节点左边的子串就是左子树，右边的子串就是右子树。然后就一直递归调用该函数，拼装后序遍历的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string postOrder(string a, string b)
{
	if (a.size() < 2)
		return a;
	else 
	{
		char root = a[0];
		int rootIndex = b.find(root);

		string leftPreStr = b.substr(0,rootIndex);
		string rightPreStr = b.substr(rootIndex+1);

		string leftInStr = a.substr(1,rootIndex);
		string rightInStr = a.substr(rootIndex+1);

		string leftPostStr = postOrder(leftInStr,leftPreStr);
		string rightPostStr = postOrder(rightInStr,rightPreStr);

		return leftPostStr + rightPostStr + root;
	}
}
文章目录
  1. 1. #1049 后序遍历