[数据结构与算法]已知二叉树的结构和中序遍历，构造树并输出层次遍历——PAT (Advanced Level) 1099 Build A Binary Search Tree (30 分)

题目概述：
给出一颗二叉树的节点连接方式，和一组树，然后根据BST的规则填入

题目分析：
1.建立结构体node记录val，left和right
2.存入每个节点的left和right
3.存入val，并排序，BST的中序遍历恰好为从小到大
4.填充val，进行dfs：参数两个root和level，root是当前根的index，level顺手记录层数
5.dfs中记录最大层数，以及三行精髓：

   if(nodelist[root].left != -1) dfs(nodelist[root].left, level + 1);
    nodelist[root] = {val[cnt++], nodelist[root].left, nodelist[root].right};//放入值，核心代码
    if(nodelist[root].right != -1) dfs(nodelist[root].right, level + 1);

左根右的思想，若左有继续深搜，直到搜不到，然后填充值（注意填充值的写法），之后再寻找右；这里体现的就是中序的左根右思想；如果给的是先序，就是先填充再左右深搜；若是后续就是先左右深搜，再填充；

这里一并解决了在给定树的结构下，先中后三种序列的树的填充dfs写法

6.最后是逐层输出，用vector<vector>记录maxlevel层的信息，注意输出的不是index，而是index对应的val，输出完当层的val后，判断左右孩子若不为空则加入到v[i + 1]中以供后续的层次遍历

完整代码：

#include<bits/stdc++.h>
using namespace std;
int n, cnt = 0, maxlevel = 0;

struct node
{
    int val, left, right;
}nodelist[110];
vector<int> val;//记录实际值

void dfs(int root, int level)
{
    maxlevel = max(level, maxlevel);
    //左根右放值,包含回溯了
    if(nodelist[root].left != -1) dfs(nodelist[root].left, level + 1);
    nodelist[root] = {val[cnt++], nodelist[root].left, nodelist[root].right};//放入值，核心代码
    if(nodelist[root].right != -1) dfs(nodelist[root].right, level + 1);
}

int main()
{
    cin >> n;
    val.resize(n);
    for(int i = 0; i < n; i++) cin >> nodelist[i].left >> nodelist[i].right;
    for(int i = 0; i < n; i++) cin >> val[i];
    sort(val.begin(), val.end());//中序遍历就是从小到大
    dfs(0, 0);
    vector<vector<int>> v;//记录每层状况，记录的是index不是val
    v.resize(n);
    v[0].push_back(0);
    for(int i = 0; i <= maxlevel; i++)
    {
        for(int j = 0; j < v[i].size(); j++)
        {
            if(i != 0) cout << " ";
            cout << nodelist[v[i][j]].val;
            if(nodelist[v[i][j]].left != -1) v[i + 1].push_back(nodelist[v[i][j]].left);
            if(nodelist[v[i][j]].right != -1) v[i + 1].push_back(nodelist[v[i][j]].right);
        }
    }
    return 0;
}

总结：
1.给定树的结构+先/中/后序对树进行填充的dfs
2.利用二维数组进行层次遍历的方法，需要提前知道maxlevel，然后遍历完一层的同时扫描其孩子进行下一层的填充；这叫未雨绸缪，环环相扣！