#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> res;
struct Node{
Node* left;
Node* right;
int val;
Node(int x): val(x), left(nullptr), right(nullptr){}
};
Node* buildTree(vector<int>& nums){
int n = nums.size();
vector<Node*> v(n);
// 建立节点
for(int i=0;i<n;i++){
if(nums[i] != -1){
v[i] = new Node(nums[i]);
}
}
// 关联左右指针
for(int i=0;i<n;i++){
if(v[i]){
if(2*i+1<n) v[i]->left = v[2*i+1];
if(2*i+2<n) v[i]->right = v[2*i+2];
}
}
return v[0];
}
vector<vector<int>> bfs(Node* root){
if(!root) return res;
queue<Node*> q;
q.push(root);
while(q.size()){
int sz = q.size();
vector<int> v;
for(int i=0;i<sz;i++){
Node* t = q.front();
q.pop();
v.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
res.push_back(v);
}
return res;
}
int main() {
vector<int> nums;
int x;
while(cin >> x){
nums.push_back(x);
}
auto root = buildTree(nums);
auto res = bfs(root);
for(const vector<int>& v : res){
for(const int& x : v){
cout<<x<<" ";
}
cout<<endl;
}
return 0;
}
测试用例:
输入:
3 5 7 -1 -1 5 28
输出:
3
5 7
5 28