L2-011 play with binary tree

Topic link
Similar topics
L2-006 Tree traversal

step ：
1、 Establish binary tree according to preorder traversal and inorder traversal
2、 Recursively flip left and right subtrees
3、 Use the first in first out property of the queue to realize hierarchical traversal （ breadth-first ）

#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
using namespace std;
int A[35];
int B[35];
int N;
typedef struct TNode {
    
	struct TNode* left;
	struct TNode* right;
	int data;
}*Tree;
Tree BuildTree(int X[],int Y[],int n) {
    		// Build a binary tree 
	if (n <= 0  )	return NULL;
	int i = 0;
	while (X[i] != Y[0])i++;
	//cout << n << endl;
	Tree p = (Tree)malloc(sizeof(struct TNode));
	p->data = X[i];
	//cout << "left" << endl;
	p->left = BuildTree(X, &Y[1], i);
	//cout << "right" << endl;
	p->right = BuildTree(&X [ i + 1], &Y [ i + 1], n - i - 1);
	
	return p;
}
void Reverse(Tree& T) {
    			// Flip left and right subtrees 
	if (T == NULL)	return;
	Reverse(T->left);
	Reverse(T->right);
	TNode* temp = T->left;
	T->left = T->right;
	T->right = temp;
}
vector<int> Level(Tree T) {
    			// Level traversal 
	queue<TNode*> Q;
	vector<int> ans;
	Q.push(T);
	while (!Q.empty()) {
    
		TNode* p = Q.front();
		Q.pop();
		if (p->left != NULL)	Q.push(p->left);
		if (p->right != NULL)Q.push(p->right);
		ans.push_back(p->data);
	}
	return ans;
}
int main() {
    
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> B[i];
	Tree root = BuildTree(A, B, N);
	Reverse(root);
	vector<int> ans = Level(root);
	for (int i = 0; i < N; i++) {
    
		cout << ans[i];
		if (i != N - 1)	cout << " ";
	}
	return 0;
}