给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
- 后序+中序->前序
因为输出顺序是根，左树，右树，就可以先处理根，然后递归的处理左树，再递归的处理右树
每一步进行处理时先根据结点node在后序中的下标输出node（下标时调用函数时就已知的），接下来递归，需要知道左，右子树根在后序中的下标，
左子树根的下标=根后序下标-右子树的长度-1
右子树的长度=树中序中最后一个结点的下标-根的中序下标
树的中序下标，根据后序下标索引到值，然后在中序中for循环找，要注意这里不是朝找整个中序数组，而是以该点为根的树在中序中的起始与结尾这段
所以递归时还应该传入以该节点为根的树在中序中起始点与结尾点的下标
左子树的开始=它父节点为根的树的开始
左子树的结束=父节点中序下标-1
右子树根的下标=父节点后序下标-1
右子树的开始=父节点中序下标+1
右子树的结束=它父节点为根的树的结束
注意在中序中找根时，若根中序下标等于start说明没有左树，若等于end说明没有右树
那么递归到下一轮的时候就会造成start>end就可以return了
求参数示意图
#include <iostream>
#define N 31
using namespace std;
int back[N], mid[N];
void front(int kb, int start, int end)
{
if (start > end)
return;
cout << back[kb]<<" ";
int i = start;
for (; i <= end; ++i) {
if (mid[i] == back[kb])
break;
}//如果没有左子树的话i就会等于start
//没有右子树i等于end
//就会造成递归调用左右子树时的start>end
int km = i;
int lkb = kb - (end - km) - 1;
int lstart = start;
int lend = km - 1;
int rkb = kb - 1;
int rstart = km + 1;
int rend = end;
front(lkb, lstart, lend);
front(rkb, rstart, rend);
}
int main()
{
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> back[i];
}
for (int i = 0; i < n; ++i) {
cin >> mid[i];
}
front(n-1, 0, n - 1);
system("pause");
return 0;
}
- 后序+中序->层序
在前面转前序的基础上就只要修改一些就先行了
由于递归是处理完了左树才处理右树的
但层序遍历并不是输完了左树才树右树的
所以下面这部很重要
在以前序的顺序访问到每个点时，不将它输出，将他们保存起来并有一个标记可以标识等会儿的输出顺序
这里定义一个index的向量，index的索引代表满二叉树中层序时每个结点的编号，值就代表结点的值，一开始把值全初始化为-1表示该索引下还没有值
然后递归调用时再传入该结点在这棵满树上应该放的位置的索引，然后利用后序下标把值赋给这个索引，计算左右子树的索引就可以利用2i+1,2i+2（下标从0开始）
最后在遍历这个index遇到非-1的输出，若输出的数量达到n了就不再遍历了
#include <iostream>
#include <vector>
#define N 31
using namespace std;
int back[N], mid[N];
vector<int> index(100000,-1);
void front(int kb, int start, int end,int ind)
{
if (start > end)
return;
//=======修改部分=================================
index[ind]=back[kb];
//===============================================
int i = start;
for (; i <= end; ++i) {
if (mid[i] == back[kb])
break;
}//如果没有左子树的话i就会等于start
//没有右子树i等于end
//就会造成递归调用左右子树时的start>end
int km = i;
int lkb = kb - (end - km) - 1;
int lstart = start;
int lend = km - 1;
int rkb = kb - 1;
int rstart = km + 1;
int rend = end;
front(lkb, lstart, lend,ind*2+1);
front(rkb, rstart, rend,ind*2+2);
}
int main()
{
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> back[i];
}
for (int i = 0; i < n; ++i) {
cin >> mid[i];
}
front(n-1, 0, n - 1,0);
int cnt=0;
for(int i=0;i<index.size()&&cnt<=n;++i){
if(index[i]!=-1){
if(i)
cout<<" ";
cout<<index[i];
++cnt;
}
}
return 0;
}
以上参考：https://www.liuchuo.net/archives/2093
- 另一个思路
声明一个结构体node，成员有这个点的值value，以这个值为根的树的开始中序中下标start，结束end，这个值的后序下标
然后利用队列
一开始把后序中最后一个结点入队，start是0，end是n-1，后序下标是n-1
每出队一个点就输出这个点的value，并计算出它左右孩子的以上参数，并且入队，计算方法和前面相同
注意当根中序下标为start就没有左孩子，为end就没有有孩子，这两种情况是不用入队的
因为层序遍历本身就是采用队列的，所以感觉还挺有道理的
代码实现改天补
网友评论