“側(cè)影”就是從左側(cè)或者右側(cè)去觀察物體所看到的內(nèi)容。例如上圖中男生的側(cè)影是從他右側(cè)看過去的樣子，叫“右視圖”；女生的側(cè)影是從她左側(cè)看過去的樣子，叫“左視圖”。

520 這個(gè)日子還在打比賽的你，也就抱著一棵二叉樹左看看右看看了……

我們將二叉樹的“側(cè)影”定義為從一側(cè)能看到的所有結(jié)點(diǎn)從上到下形成的序列。例如下圖這棵二叉樹，其右視圖就是 { 1, 2, 3, 4, 5 }，左視圖就是 { 1, 6, 7, 8, 5 }。

于是讓我們首先通過一棵二叉樹的中序遍歷序列和后序遍歷序列構(gòu)建出一棵樹，然后你要輸出這棵樹的左視圖和右視圖。

輸入格式：
輸入第一行給出一個(gè)正整數(shù) N (≤20)，為樹中的結(jié)點(diǎn)個(gè)數(shù)。隨后在兩行中先后給出樹的中序遍歷和后序遍歷序列。樹中所有鍵值都不相同，其數(shù)值大小無關(guān)緊要，都不超過 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

基本思路：
本道題是經(jīng)典的二叉樹遍歷問題。首先根據(jù)后序遍歷和中序遍歷創(chuàng)建一個(gè)數(shù)組，隨后開一個(gè)多維的vector數(shù)組。從二叉樹的根結(jié)點(diǎn)開始dfs遍歷。因?yàn)閐fs遍歷的時(shí)候，是從左往右的，所以同一深度的結(jié)點(diǎn)在vector[depth]里面一定是按照從左往右的順序排列的。我們再看題目，不難發(fā)現(xiàn)從右邊看二叉樹實(shí)際上就是每個(gè)vector[deep]中最右邊的結(jié)點(diǎn)，即vector[deep]中的最后一個(gè)元素;同理從左邊看二叉樹，每層看到的結(jié)點(diǎn)實(shí)際上是vector[deep]中的第一個(gè)元素。最后按照輸出樣例輸出即可。

參考代碼：

#include <iostream> #include <vector> using namespace std; int n, hou[25], zhong[25]; struct tree{int data;tree *left,*right; };tree* creat(int root, int begin, int end){if(end < begin)return NULL;tree *t = new tree();t->data = hou[root];int i;for(i = begin; hou[root] != zhong[i]; i++);t->left = creat(root-1-(end-i), begin, i-1);t->right = creat(root-1, i+1, end);return t; }vector<int> v[105]; void dfs(tree* t, int level) {if(t == NULL)return;level++;v[level].push_back(t -> data);if(t -> left)dfs(t -> left, level);if (t -> right)dfs(t -> right, level); }int main(){scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &zhong[i]);for(int i = 0; i < n; i++)scanf("%d", &hou[i]);tree *t = creat(n-1, 0, n-1);dfs(t, 0);printf("R:");for(int i = 1; i <= 20; i++){if(v[i].size() == 0)break;printf(" %d", v[i][v[i].size()-1]);}printf("\nL:");for(int i = 1; i <= 20; i++){if(v[i].size() == 0)break;printf(" %d", v[i][0]);}printf("\n");return 0; }

總結(jié)

以上是生活随笔為你收集整理的520 钻石争霸赛 7-8浪漫侧影（二叉树的遍历）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。