example

• https://pintia.cn/problem-sets/994805342720868352/problems/994805365537882112
  

#include <iostream>
#include <queue>
#define maxSize 10
using namespace std;

typedef struct BTNode {
	int left = -1;
	int right = -1;
}BTNode;

void arr2BTree(char arr[][2], int n, BTNode* bTree) {
	for (int i = 0; i < n; ++i) {
		if (arr[i][0] != '-') {
			bTree[i].left = arr[i][0] - '0';
		}
		if (arr[i][1] != '-') {
			bTree[i].right = arr[i][1] - '0';
		}
	}
}
int findRoot(BTNode* bTree, int n) {
	//找到根节点的位置
	int* hash = new int[n];
	for (int i = 0; i < n; ++i) {
		hash[i] = 0;
	}
	for (int i = 0; i < n; ++i) {
		hash[bTree[i].left] = 1;//不是根节点
		hash[bTree[i].right] = 1;//不是根节点 
	}
	for (int i = 0; i < n; ++i) {
		//找一下谁是根节点
		if (hash[i] == 0) {
			return i;//i是根节点 
		}
	}
	return 0;
}
void printInvertedLevelOrder(BTNode bTree[], int n, int root) {//打印层次遍历，但每层是从右往左
	queue<int> que;
	que.push(root);
	int temp;
	int count = 0;
	while (que.size() != 0) {
		temp = que.front();
		que.pop();//出队
		if (bTree[temp].right != -1) {
			que.push(bTree[temp].right);
		}
		if (bTree[temp].left != -1) {
			que.push(bTree[temp].left);
		}
		++count;
		if (count != n) {
			cout << temp << " ";
		}
		else {
			cout << temp;
		}

	}
}
void printInvertedInOrder(BTNode bTree[], int &flag, int root) {//打印中序，但是是右-中-左
	//调用时，flag为1,代表是根节点，以后每次递归时，都将flag设为0
	
	if (bTree[root].right != -1) {
		printInvertedInOrder(bTree, flag, bTree[root].right);
	}
	if (flag == 1) {
		cout << root;
		flag--;
	}
	else {
		cout << " " << root;
	}
	if (bTree[root].left != -1) {
		printInvertedInOrder(bTree, flag, bTree[root].left);
	}
	
	

}
int main() {
	int n;
	cin >> n;
	char arr[maxSize][2];
	for (int i = 0; i < n; ++i) {
		cin >> arr[i][0] >> arr[i][1];
	}
	BTNode* bTree = new BTNode[n];
	arr2BTree(arr, n, bTree);
	int root = findRoot(bTree, n);
	printInvertedLevelOrder(bTree, n, root);
	cout << endl;
	int flag = 1;
	printInvertedInOrder(bTree, flag, root);
	return 0;

}