階層遍歴に基づいて完全なツリーを再構築する
12211 ワード
#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;
}