[PTA] l2-011 play with binary tree

Original link

L2-011 Play with binary trees

Their thinking

Make use of the characteristics of preorder traversal and middle order traversal for deep search
Deep search exit conditions ： Middle Preface >= The tail does not hold
Deep search recursion ： Change the root node , The beginning and end of the middle order point to , Store subscript
The main points of ： Find the root of the middle order from the previous order

ac Code

#include <iostream>
#include <cstring>
using namespace std;
int in[30], pre[30];
int level[100000];// The array should be a little larger , Because it's not a complete binary tree  

void dfs(int root, int start, int end, int index) {
    
	//root The first of preorder traversal  start,end The beginning and end of middle order traversal  index Stored subscript 
	if(start > end) return;
	
	level[index] = pre[root];// this （ Son ） Root node of tree , Store 
	
	int i = start;
	while(i < end && in[i] != pre[root]) i++;// Find the root node in the middle order traversal  （ This is also the separation point of the left and right subtrees of the preorder traversal ）

	dfs(root + 1, start, i - 1, 2 * index + 2);// Here, the node is cleverly changed , Change the left and right nodes .
	dfs(root + (i - start) + 1, i + 1, end, 2 * index + 1);
}

int main() {
    
	memset(level, -1, sizeof(level));

	int n;
	scanf("%d",&n);
	for(int i = 0; i < n; i++) scanf("%d", &in[i]);
	for(int i = 0; i < n; i++) scanf("%d", &pre[i]);

	dfs(0, 0, n - 1, 0);

	int cnt = 0;
	for(int i = 0; i < 10000; i++) {
    
		if(level[i] != -1) {
    
			if(cnt != n - 1) {
    
				printf("%d ", level[i]);
				cnt++;
			} else{
    
				printf("%d", level[i]);
				break;
			}
		}
	}
	return 0;
}