二叉树重建

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

中序遍历 左-根-右

vector<int> pre,in,post，level;
unordered_map<int,int> hash;
for(int i=0;i<in.size();i++)
    hash[in[i]]=i;

给定数的前序遍历，中序遍历

hash用于确定左右子树的大小
前序遍历 根-左-右

TreeNode* dfs(int pl,int pr,int il,int ir)
{
    if(pl>pr) return NULL;
    int root_val=pre[pl];//根节点值
    int root_in=hash[root_val];//根节点在中序遍历的下标
    auto root=new TreeNode(root_val);
    int l_len=root_in-1-il+1;
    int r_len=ir-(root_in+1)+1;
    auto left=dfs(pl+1,pl+1+l_len-1,il,root_in-1);
    auto right=dfs(pl+1+l_len,pl+1+l_len+r_len-1,root_in+1,ir);
    root->left=left;
    root->right=right;
    return root;


}

给定数的后序遍历，中序遍历

hash用于确定左右子树的大小
后序遍历 左-右-根

TreeNode* dfs(int pl,int pr,int il,int ir)
{
    if(pl>pr) return NULL;
    int root_val=post[pr];//根节点值
    int root_in=hash[root_val];//根节点在中序遍历的下标
    auto root=new TreeNode(root_val);
    int l_len=root_in-1-il+1;
    int r_len=ir-(root_in+1)+1;
    auto left=dfs(pl,pl+l_len-1,il,root_in-1);
    auto right=dfs(pl+l_len,pl+l_len+r_len-1,root_in+1,ir);
    root->left=left;
    root->right=right;
    return root;


}

给定树的层序遍历，中序遍历

hash用于判定左右儿子是否存在

    int len_l=level.size()
    bool st[N]={0};//层序遍历中的点是否被遍历过
    auto root=new TreeNode(level[0]);
    TreeNode* q[N];
    q[0]=root;

    while(int i=0,j=1;j<level.size();)//逐层遍历,i为当前层起点，j为下一层起点
    {
        for(int end=j;i<end;i++)//遍历当前层
        {
            int p=hash[level[i]];//当前点在中序遍历中的位置
            st[p]=true;//表示遍历过当前点
            //判断是否有左子节点
            //若当前点存在左子节点，则该节点在中序遍历的下标一定为p-1，
            //且该点没有被遍历过,因为层序遍历，父节点一定先于子节点被遍历到
            if(p-1>=0 && !st[p-1])
            {
                q[i]->left=new TreeNode(level[j]);
                q[j++]=q[i]->left
            }
            //判断是否有右子节点
            //若当前点存在右子节点，则该节点在中序遍历的下标一定为p+1，
            //且该点没有被遍历过,因为层序遍历，父节点一定先于子节点被遍历到
            if(p+1<level.size() && !st[p+1])
            {
                q[i]->right=new TreeNode(level[j]);
                q[j++]=q[i]->right;
            }
        }
    }
    //重建二叉树的根为root