階層遍歴に基づいて完全なツリーを再構築する


#include
#include
#include
using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {};
};

void insert(TreeNode* node,vector<int> arr,int i)
{
    int len=(int)arr.size();
    if(i>=len)					//          
        return;
    node->val=arr[i];			//      
    if(2*(i+1)-1 <= len-1)		//              ,              
    {
        TreeNode* l=new TreeNode(NULL);	//      
        node->left=l;				//              
        insert(l,arr,2*(i+1)-1);	//    
    }
    if(2*(i+1) <= len-1)		//              ,              
    {
        TreeNode* r=new TreeNode(NULL);	//      
        node->right=r;				//              
        insert(r,arr,2*(i+1));		//    
    }
}

//       ,  insert()         
TreeNode* ConTree(vector<int> arr)
{
    TreeNode* node=new TreeNode(NULL);
    insert(node,arr,0);
    return node;
}

void inOrder(TreeNode* node)
{
    if(node==NULL)				//     ,  
        return;
    inOrder(node->left);		//         ,  ,    
    cout<<node->val<<" ";		//     ,     
    inOrder(node->right);		//         ,  ,    
}

int main()
{
    vector<int> arr;
    int n,index,a;
    cin>>n;					//           
    index=pow(2,n)-1;		//               n  -1
    while(index--)
    {
        cin>>a;
        arr.push_back(a);
    }
    TreeNode* root=ConTree(arr);
    inOrder(root);
    cout<<endl;
    return 0;
}