1099. Build A Binary Search Tree

PAT-A1099，题目地址：https://www.patest.cn/contests/pat-a-practise/1099
这道题目和PAT-A1064有点像，主要思路还是要还原树，如果树还原好了，那么层序遍历也就简单了。
主要思路如下，以给出的示例为例：

1. 将数据从小到大排序（11，25，38，42，45，58，67，73，82）
2. 根据树的结构给出中序遍历下标的结果（2，1，3，5，4，0，7，8，6）
3. 将上面两个结果一一对应即可还原出树（58，25，11，38，45，42，82，67，73）
4. 进行层序遍历（58 25 82 11 38 67 45 73 42）

如下图：

代码如下：

#include <iostream>
#include <algorithm>
#include <queue>

struct Node{
    int left;
    int right;
    int parent;
    Node(): left(-1), right(-1), parent(-1){}
};

int main(){
    int n;
    Node nodes[100];
    int nums[100];
    int tree[100];
    std::cin >> n;
    for(int i = 0; i < n; i++){
        std::cin >> nodes[i].left >> nodes[i].right;
        if(nodes[i].left != -1)
            nodes[nodes[i].left].parent = i;
        if (nodes[i].right != -1)
            nodes[nodes[i].right].parent = i;
    }
    for(int i = 0; i < n; i++){
        std::cin >> nums[i];
    }
    std::sort(nums, nums + n); //第1步
    int index = 0, now = 0;
    while(nodes[now].left != -1){
        now = nodes[now].left;
    }
    while(1){ //对tree进行中序遍历，now是当前所在的节点的下标
        tree[now] = nums[index++];
        if(nodes[now].right != -1){
            now = nodes[now].right;
            while(nodes[now].left != -1){
                now = nodes[now].left;
            }
        }
        else if(now == 0 || now == nodes[nodes[now].parent].left){
            now = nodes[now].parent;
        }
        else{
            while(now != 0 && now == nodes[nodes[now].parent].right){
                now = nodes[now].parent;
            }
            now = nodes[now].parent;
        }
        if(now == -1){
            break;
        }
    } //这个之前为第2、3步

    std::queue<int> q; //利用队列对tree进行层序遍历
    q.push(0);
    while(!q.empty()){
        int tmp = q.front();
        q.pop();
        if(nodes[tmp].left != -1)
            q.push(nodes[tmp].left);
        if(nodes[tmp].right != -1)
            q.push(nodes[tmp].right);
        if(tmp != 0){
            std::cout << " ";
        }
        std::cout << tree[tmp];
    }
    std::cout << std::endl;
    return 0;
}