7-8 romantic profile (25 points) achievements + new problem solving ideas

Romantic silhouette (25 branch )

Title Description

“ Profile ” Is to observe what the object sees from the left or right . For example, the silhouette of the boy in the above picture is what he looks at from his right side , It's called “ Right side view ”; The girl's silhouette looks from her left , It's called “ Left view ”.
We will the of binary tree “ Profile ” Defined as a sequence of all nodes visible from one side from top to bottom . For example, the binary tree in the figure below , The right view is { 1, 2, 3, 4, 5 }, The left view is { 1, 6, 7, 8, 5 }.

So let's first build a tree through the middle order traversal sequence and post order traversal sequence of a binary tree , Then you have to output the left and right views of the tree .

Input format ：

The first line of input gives a positive integer N (≤20), Is the number of nodes in the tree . Then, the middle order traversal and post order traversal sequences of the tree are given in two lines . All key values in the tree are different , Its value is irrelevant , Not more than int The scope of the .

Output format ：

The first line outputs the right view , The second line outputs the left view , The format is shown in the example .

sample input ：
8
6 8 7 4 5 1 3 2
8 5 4 7 6 3 2 1
sample output ：
R: 1 2 3 4 5
L: 1 6 7 8 5

analysis

1） Jianshu writes directly according to the template , Then get tree Array .
2） The right side of the output is from index=1 Start , If index×2+1 If there is a node, output , If it doesn't exist, check index×2, If it exists, output , It doesn't exist, just from index×2 Start , Go to front The first node found is The most right The node of .
3） The output left side is similar to the right side , If index×2 If there is a node, output , If it doesn't exist, check index×2+1, If it exists, output , It doesn't exist, just from index×2 Start , Go to after The first node found is Leftmost left The node of .

Code

#include <iostream>
#include <algorithm>
#include <cmath>

#define MAX 100000

using namespace std;

int n, midord[30], postord[30], tree[MAX], level = 0;

void createTree (int *postord, int *midord, int n, int index) {
    
    if (!n) return ;
    int k = 0;
    while (postord[n - 1] != midord[k]) k ++;
    tree[index] = midord[k];
    level = max(level, index);
    
    createTree(postord, midord, k, index * 2);
    createTree(postord + k, midord + k + 1, n - k - 1, index * 2 + 1);
}

int main () {
    
    cin >> n;
    
    for (int i = 0; i < n; i ++) cin >> midord[i];
    for (int i = 0; i < n; i ++) cin >> postord[i];
    
    createTree(postord, midord, n, 1);
    
    for (int i = 1; i <= 22; i ++)
        if (level < pow(2, i)) {
    
            level = i;
            break;
        }
    
    cout << "R: ";
    int cnt = 0, idx = 1;
    while (cnt < level) {
    
        if (tree[idx]) cout << tree[idx];
        
        if (tree[idx * 2 + 1]) idx = idx * 2 + 1;
        else if (tree[idx * 2]) idx = idx * 2;
        else {
    
            idx = idx * 2;
            while (!tree[idx]) idx --;
        }
        
        cnt ++;
        if (cnt != level) cout << ' ';
        else cout << endl;
    }
    
    cout << "L: ";
    cnt = 0, idx = 1;
    while (cnt < level) {
    
        if (tree[idx]) cout << tree[idx];
        
        if (tree[idx * 2]) idx = idx * 2;
        else if (tree[idx * 2 + 1]) idx = idx * 2 + 1;
        else {
    
            idx = idx * 2;
            while (!tree[idx]) idx ++;
        }
        
        cnt ++;
        if (cnt != level) cout << ' ';
        else cout << endl;
    }
    
    return 0;
}