题解 )"/>

浪漫侧影 ( 题解 )

“侧影”就是从左侧或者右侧去观察物体所看到的内容。例如上图中男生的侧影是从他右侧看过去的样子，叫“右视图”；女生的侧影是从她左侧看过去的样子，叫“左视图”。

520 这个日子还在打比赛的你，也就抱着一棵二叉树左看看右看看了……

我们将二叉树的“侧影”定义为从一侧能看到的所有结点从上到下形成的序列。例如下图这棵二叉树，其右视图就是 { 1, 2, 3, 4, 5 }，左视图就是 { 1, 6, 7, 8, 5 }。

于是让我们首先通过一棵二叉树的中序遍历序列和后序遍历序列构建出一棵树，然后你要输出这棵树的左视图和右视图。

输入格式：

输入第一行给出一个正整数 N (≤20)，为树中的结点个数。随后在两行中先后给出树的中序遍历和后序遍历序列。树中所有键值都不相同，其数值大小无关紧要，都不超过 int 的范围。

输出格式：

第一行输出右视图，第二行输出左视图，格式如样例所示。

输入样例：

8
6 8 7 4 5 1 3 2
8 5 4 7 6 3 2 1

输出样例：

R: 1 2 3 4 5
L: 1 6 7 8 5

个人思路：

此题有两个考点，首先是根据树的中序遍历和其余任意遍历（前序遍历，后序遍历，层序遍历）构建一颗二叉树，其次是对一颗二叉树的层序遍历。

做法：

根据遍历建好二叉树，再进行层序遍历，当进行至每两层的交接点时，恰好是上一层的“右视图”，和下一层的“左视图”，将其值记录下来，注意要处理特殊情况，头节点和最下层的右视图。

最后将结果输出。

1.建树

由于要保存左右子节点，树的高度，每个节点的值，所以选择结构体建树。

通过递归的方式，分别处理前序和中序遍历，注意每棵子树对应遍历的起点和终点。

2.遍历

普通层序遍历，加入对高度的判断即可。

AC代码（注释解释）：

#include <bits/stdc++.h>
using namespace std;
const int N = 21;
int l[N], r[N], in[N], post[N];//l,r分别为左右视图数组，in中序，post后序
int z=0, y=0 ,n, m;            //z左，y右
typedef struct Node* pnode;
struct Node {int data;   //数据int h;      //高度pnode l, r;
};
typedef pnode Tree;
//il,ir分别为中序遍历起点和终点，pl,pr分别为后序遍历起点和终点
Tree create(int il, int ir, int pl, int pr, int high) {Tree t;if (pl > pr) return NULL;  //此时对应子树为空，返回NULLt = (pnode)malloc(sizeof(struct Node));t->data = post[pr];        //后序遍历每一段最后一个就是根节点t->h = high;int i = il;while(in[i] != post[pr]) i++;  //用i找到根节点对应的中序遍历中的位置t->l = create(il, i - 1, pl, pl + i - 1 - il, high + 1);t->r = create(i + 1, ir, pl + i - il, pr - 1, high + 1);return t;   //递归建树
}void Bianli(Tree t) {pnode p, pre=NULL;queue<Tree> q;if (t == NULL) return;q.push(t);while (!q.empty()) {p = q.front();q.pop();if (pre == NULL) l[z++] = p->data;  //对头节点的处理else {if (p->h != pre->h) {l[z++] = p->data;r[y++] = pre->data;}}pre = p;if (p->l) q.push(p->l);if (p->r) q.push(p->r);}r[y++] = p->data;      //对最后一个右视图的处理
}int main() {cin >> n;for (int i = 0; i < n; i++)cin >> in[i];for (int i = 0; i < n; i++)cin >> post[i];Tree t = create(0, n - 1, 0, n - 1, 0);Bianli(t);cout << "R:";for (int i = 0; i < z; i++)cout << " " << r[i];cout << endl << "L:";for (int i = 0; i < y; i++)cout << " " << l[i];cout << endl;return 0;}