Build A Binary Search Tree (30

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define Null -1
using namespace std;
struct tree{
    int left;
    int right;
    int data;
};
int main(){
    int N;
    cin>>N;
    int keys[N];
    tree Tree[N];
    vector<int> v;
    queue<int> q;
    vector<tree> order;
    for(int i=0;i<N;i++){
        cin>>Tree[i].left>>Tree[i].right;
    }
    for(int i=0;i<N;i++){
        cin>>keys[i];
    }
    sort(keys,keys+N);
    int T = 0,i=0;
    while(T!=-1||!v.empty()){
        while(T!=-1){
            v.push_back(T);
            T = Tree[T].left;
        }
        if(!v.empty()){
            T = v.back();
            v.pop_back();
            Tree[T].data = keys[i];
            i++;
            T = Tree[T].right;
        }
    }
    T = 0;
    q.push(T);
   while(!q.empty()){
       T = q.front();
       if(Tree[T].left!=Null)
       q.push(Tree[T].left);
       if(Tree[T].right!=Null)
       q.push(Tree[T].right);
       cout<<Tree[T].data;
       if(q.size()>1)
           cout<<" ";
      q.pop();
   }
}

//思路：显然BST的中序遍历对应从小到大的排列。
//然后利用排序建树，再bfs按层输出即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e2+5;
int n,cnt,ok=1,data[maxn],lch[maxn],rch[maxn],A[maxn];
void build(int rt){
    if(rt==-1) return ;
    build(lch[rt]);
    data[rt]=A[++cnt];
    build(rch[rt]);
}
void bfs(){    
    queue<int> que;
    que.push(0);
    while(!que.empty()){
        int tmp=que.front();que.pop();
        if(ok){ ok=0;printf("%d",data[tmp]);}
        else { printf(" %d",data[tmp]);}
        if(lch[tmp]!=-1) que.push(lch[tmp]);
        if(rch[tmp]!=-1) que.push(rch[tmp]);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d %d",&lch[i],&rch[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&A[i]);
    sort(A+1,A+1+n);
    build(0);bfs();
    return 0;
} 

//思路远没有上面几位同学的简洁，没有想到中序遍历，
//而是 考虑节点的左侧节点总数，右侧节点的总数,以及父节点的排名，确定 该节点的排名~~~~；
#include<stdio.h>
#include<stdlib.h>
typedef struct QNode{
	    int data;
	    struct QNode *next;
} QNode;
typedef struct{
	QNode *front;
	QNode *rear;
} LinkQueue;
int InitQueue(LinkQueue &L){
	L.front=L.rear=(QNode *)malloc(sizeof(QNode));
	if(!L.front) exit(0);
	L.front->next=NULL;
	return 1;
}
int QueueEmpty(LinkQueue L){
	if(L.front==L.rear) return 1;
	else return 0;
}
int EnQueue(LinkQueue &L, int e){
	QNode *p;
	p=(QNode *)malloc(sizeof(QNode));
	if(!p) exit(0);
	p->data=e; p->next=NULL;
	L.rear->next=p;
	L.rear=p;
	return 1;
}
int DeQueue(LinkQueue &L, int &e){
	QNode *p;
	if(L.front==L.rear) return 0;
	p=L.front->next;
	e=p->data;
	L.front->next=p->next;
	if(L.rear == p) L.rear=L.front;
	free(p);
	return 1;	
}

typedef struct{
        int lchildId;
        int rchildId;
        int lchildNum;
        int rchildNum;
        int rank;
       } BStree;
int childNumCount(BStree treeList[], int startId){
	 if(treeList[startId].lchildId==-1)
	   treeList[startId].lchildNum=0;
	 else
	   treeList[startId].lchildNum=childNumCount(treeList,treeList[startId].lchildId)+1;
 	 
     if(treeList[startId].rchildId==-1)
        treeList[startId].rchildNum=0;
 	 else 
	    treeList[startId].rchildNum=childNumCount(treeList,treeList[startId].rchildId)+1;
	 
	 return treeList[startId].lchildNum + treeList[startId].rchildNum;	 
}
void rankCount(BStree treeList[], int curId, int parentRank, int preChild){
	if(!preChild) treeList[curId].rank=parentRank-treeList[curId].rchildNum-1;
	else treeList[curId].rank=parentRank+treeList[curId].lchildNum+1;
	if(treeList[curId].lchildId!=-1)
		rankCount(treeList,treeList[curId].lchildId,treeList[curId].rank,0);
		
	if(treeList[curId].rchildId!=-1)
	     rankCount(treeList,treeList[curId].rchildId,treeList[curId].rank,1);
}

void listOutPut(BStree treeList[], int list[]){
	 LinkQueue L;
	 int parent,child;
	 InitQueue(L);
	 printf("%d",list[treeList[0].rank]);
	 child=treeList[0].lchildId;
	 if(child!=-1) EnQueue(L,child);
	 child=treeList[0].rchildId;
	 if(child!=-1) EnQueue(L,child);
	 while(!QueueEmpty(L)){
 		DeQueue(L,parent);
		printf(" %d",list[treeList[parent].rank]);
		child=treeList[parent].lchildId;
		if(child!=-1) EnQueue(L,child);
		child=treeList[parent].rchildId;
		if(child!=-1) EnQueue(L,child);
 	}
 	printf("\n");
} 

int QsortPartition(int list[],int low,int high){
	int temp;
	temp=list[low];
	while(low<high){
		while(temp<=list[high] && low<high) high--;
		list[low]=list[high];
		while(temp>=list[low] && low<high) low++;
		list[high]=list[low];
	}
	list[low]=temp;
	return low;
}
void Qsort(int list[], int low, int high){
	int median;
	if(low<high){
	  median=QsortPartition(list,low,high);
	  Qsort(list,low,median-1);
	  Qsort(list,median+1,high);  
	}
} 
int main(){
	int N;
	BStree *treeList;
	int *list,i,lchild,rchild,rankRoot;
	scanf("%d",&N);
	treeList=(BStree *)malloc(N*sizeof(BStree));
	list=(int *)malloc(N*sizeof(int));
	for(i=0;i<N;i++){
		scanf("%d %d",&lchild,&rchild);
		treeList[i].lchildId=lchild;
		treeList[i].rchildId=rchild;
	}
	for(i=0;i<N;i++) scanf("%d",list+i);
	Qsort(list,0,N-1);
	childNumCount(treeList,0);
	rankCount(treeList,0,N,0);
	listOutPut(treeList,list);
}

//binary search tree
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

struct node{
	int key;
	int pos;
	node* left;node* right;
};
node* pointers[200];
vector<int> serial;
vector<int> record;//to remember which pos has which key

void midOrder(node* root){
	if(root==NULL){
		return;
	}
	midOrder(root->left);
	record.push_back(root->pos);
	midOrder(root->right);
}


void level_traverse(node* root){
	node* p=root;
	queue<node*> line;
	line.push(p);
	while(!line.empty()){
		p=line.front();
		line.pop();
		if(p->left!=NULL)line.push(p->left);
		if(p->right!=NULL)line.push(p->right);
		cout<<p->key;if(!line.empty())cout<<" ";
	}
}

int main(){
	int n,t;
	int l,r;
	cin>>n;
	for(int i=0;i<200;i++){
		pointers[i]=new node;
	} 
	for(int i=0;i<n;i++){
		cin>>l>>r;
		pointers[i]->pos=i;//
		if(l!=-1)pointers[i]->left=pointers[l];
		else pointers[i]->left=NULL;
		if(r!=-1)pointers[i]->right=pointers[r];
		else pointers[i]->right=NULL;
	}
	for(int i=0;i<n;i++){
		cin>>t;
		serial.push_back(t);
	}
	sort(serial.begin(),serial.end());
	//for(int i=0;i<serial.size();i++)cout<<serial[i]<<" ";
	//cout<<endl;
	midOrder(pointers[0]);
	for(int i=0;i<record.size();i++){
		t=record[i];
		pointers[t]->key=serial[i];
	}
	
	level_traverse(pointers[0]);
	
	return 0;
}

a = int(input())
b = [list(map(int,input().split())) for i in range(a)]
m = [-1 for i in range(a)]
m[0],n = (2 ** a,a),[0]
for i in n:
    for j in range(2):
        if b[i][j] != -1:
            m[b[i][j]] = m[i][0] - (-1) ** j * 2 ** (m[i][1] - 1),m[i][1] - 1
            n.append(b[i][j])

p = dict(zip(sorted(m),sorted(map(int,input().split()))))
print(' '.join(map(str,[p[i] for i in sorted(p,key = lambda x:(-x[1],x[0]))])))

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=110;
struct node{
    int value;
    int lchild,rchild;
}Node[maxn];
int n,data[maxn],index=0;
void create(int root){                //中序建造二叉排序树
    if(root==-1) return;              //递归边界（空结点）
    create(Node[root].lchild);
    Node[root].value=data[index++];
    create(Node[root].rchild);
}
void layerOrder(int root){            //层序遍历
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        if(Node[now].lchild!=-1) q.push(Node[now].lchild);
        if(Node[now].rchild!=-1) q.push(Node[now].rchild);
        cout<<Node[now].value;
        if(!q.empty()) cout<<" ";
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>Node[i].lchild>>Node[i].rchild;
    for(int i=0;i<n;i++)
        cin>>data[i];
    sort(data,data+n);       //将输入序列升序排序即得BST中序序列
    create(0);
    layerOrder(0);
    return 0;
} 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct {
    int val;
    int left;
    int right;
} Node;
Node node[100];
int value[100];
int cont = 0;
void travel(int v);

int main(void) {
    int n, i;
    
    cin >> n;
    for (i = 0; i < n; i++)
	cin >> node[i].left >> node[i].right;
    for (i = 0; i < n; i++)
        cin >> value[i];
	
    sort(value, value+n);
    travel(0);
	
    queue<int> q;
    q.push(0);
    cout << node[0].val;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
		if (node[v].left != -1)			q.push(node[v].left);
	    if (node[v].right != -1)		q.push(node[v].right);
        if (v != 0)     cout << " " << node[v].val;        
    }    
    cout << endl;
    
    return 0;
}

void travel(int v) {
    if (v == -1)    return;
    travel(node[v].left);
    node[v].val = value[cont++];
    travel(node[v].right);  
}

#include<iostream>
#include<cstdlib>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef struct node{
	int data;
	int Lchild;
	int Rchild;
}BiTNode,*BiTree;

void Crt_BiTree(vector<BiTree> &BT,int N){
	for(int i=0; i<N; i++){
		BT[i] = (BiTNode *)malloc(sizeof(BiTNode));
		BT[i]->data = 0;
		cin>>BT[i]->Lchild;
		cin>>BT[i]->Rchild;
	}
	return;
}

int Node_Num(vector<BiTree> &BT,int m_root){
	if(m_root == -1)
		return 0;
	int count = 1;
	queue<int> Q;
	int p = m_root;
	Q.push(p);
	while(!Q.empty()){
		p = Q.front();
		Q.pop();
		if(BT[p]->Lchild != -1){
			Q.push(BT[p]->Lchild);
			count++;
		}
		if(BT[p]->Rchild != -1){
			Q.push(BT[p]->Rchild);
			count++;
		}
	}
	return count;
}

void Log(vector<BiTree> &BT,int *Seq,int root){

	if(root == -1)
		return;
	int l_num = Node_Num(BT,BT[root]->Lchild);
//	printf("%d 号结点有 %d 个左孩子\n",root,l_num);
	BT[root]->data = *(Seq + l_num);
//	printf("将数据 %d 装载进 %d 号容器\n",*(Seq+l_num),root);
	Log(BT,Seq,BT[root]->Lchild);
	Log(BT,Seq + l_num + 1,BT[root]->Rchild);
	return;
}

void Layer_Order(vector<BiTree> &BT){
	queue<int> Q;
	int p = 0;
	Q.push(p);
	while(!Q.empty()){
		p = Q.front();
		Q.pop();
		if(Q.empty() && BT[p]->Lchild == -1 && BT[p]->Rchild == -1)
			printf("%d\n",BT[p]->data);
		else
			printf("%d ",BT[p]->data);
		if(BT[p]->Lchild != -1)
			Q.push(BT[p]->Lchild);
		if(BT[p]->Rchild != -1)
			Q.push(BT[p]->Rchild);
	}
}

int main(){
	vector<BiTree> BT;
	int N;
	cin>>N;
	BT.resize(N);
	Crt_BiTree(BT,N);
	int Seq[100];
	for(int i=0; i<N; i++)
		cin>>Seq[i];
	sort(Seq,Seq+N);
	Log(BT,Seq,0);
	Layer_Order(BT);
	return 0;
} 

//根据图中对二叉搜索树的标号方式，输入的左右子节点直接就是邻接链表啊
//原来深度优先搜索和广度优先搜索应用这么广泛
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
//输入最多100个数，直接就给它105个
int sorted[105];//按大小排好序的数组
int values[105];//根据图中二叉搜索树的标号方式形成的数组
int childs[105][2];//childs[curr][0]表示curr节点的左孩子节点
void dfs(int now, int &k) {//中序遍历（包含深度优先搜索，只要可能，先尽可能深入）
	if (now < 0) {
		return;
	}
	dfs(childs[now][0], k);
	values[now] = sorted[k];
	++k;//k是一个引用，记录已经填了几个值了
	dfs(childs[now][1], k);
}
void bfs() {//广度优先搜索
	queue<int> que;
	que.push(0);
	while (!que.empty()) {
		int v = que.front();
		que.pop();
		if (v == 0) {
			cout << values[0];
		}
		else {
			cout << " " << values[v];
		}
		//哦，这样就可以进行层序遍历，这不就是广度优先搜索吗！
		if (childs[v][0]>0)
			que.push(childs[v][0]);
		if (childs[v][1] > 0)
			que.push(childs[v][1]);
	}
	cout << endl;
}
int main() {
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	for (int i = 0;i < N;++i) {
		//输入直接就是一个邻接链表啊，一开始没发现
		cin >> childs[i][0] >> childs[i][1];
	}
	for (int i = 0;i < N;++i) {
		cin >> sorted[i];
	}
	sort(sorted, sorted + N);//原来数组也可以这样排序，我是个菜鸟
	//填值
	int c = 0;//跟踪填到第几个值了
	dfs(0, c);
	//广度优先搜索进行层序遍历
	bfs();
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector> 
#include <queue> 

using namespace std;

struct Tree
{     int left;     int right;     int data;
};

int main()
{     int N;     cin>>N;     int keys[N];     Tree T[N];     vector<int> v;     queue<int> q;     vector<Tree> order;     for(int i=0;i<N;i++)         cin>>T[i].left>>T[i].right;     for(int i=0;i<N;i++)         cin>>keys[i];     sort(keys,keys+N);     int t=0,i=0;     while(t!=-1 || !v.empty())     {         while(t!=-1)         {             v.push_back(t);             t = T[t].left;         }         if(!v.empty())         {             t = v.back();             v.pop_back();             T[t].data = keys[i];             i++;             t = T[t].right;         }     }     t = 0;     q.push(t);     while(!q.empty())     {         t = q.front();         if(T[t].left != -1)             q.push(T[t].left);         if(T[t].right != -1)             q.push(T[t].right);         cout<<T[t].data;         if(q.size()>1)             cout<<" ";         q.pop();     }     return 0;
}

	

#include<bits/stdc++.h>
using namespace std;

const int Max=110;
int n,num[Max],id;

struct Node {
	int data;
	int lchild,rchild;
} node[Max];

void Inorder(int root) {
	if(root==-1) return ;
	Inorder(node[root].lchild);
	node[root].data=num[id++];
	Inorder(node[root].rchild);
}

int sum;
void BFS(int root) {
	queue<int> q;
	q.emplace(root);
	while(!q.empty()) {
		int now=q.front();
		q.pop();
		printf("%d",node[now].data);
		sum++;
		if(sum<n) {
			printf(" ");
		}
		if(node[now].lchild!=-1) q.emplace(node[now].lchild);
		if(node[now].rchild!=-1) q.emplace(node[now].rchild);
	}
}

int main() {
	scanf("%d",&n);
	int l,r;
	for(int i=0; i<n; i++) {
		scanf("%d %d",&l,&r);
		node[i].lchild=l;
		node[i].rchild=r;
	}
	for(int i=0; i<n; i++) {
		scanf("%d",&num[i]);
	}
	sort(num,num+n);
	Inorder(0);
	BFS(0);
	printf("\n");
	return 0;
}

更多PAT甲级详解--acking-you.github.io

题目

OJ平台

题目大意

文章文字那么长，主要就掌握三点：

1. 输入给到二叉搜索树的树形结构。
2. 给出一堆数据填入这些结点中，使其满足二叉搜索树。
3. 按层序遍历输出二叉搜索树的数据。

• 好了，我们清楚了这三点后，我们最关键的就在于怎么把这棵树填充成二叉搜索树？

由于二叉搜索树的性质，它的中序遍历正好就是从小到大的序列，诶！这不正好可以利用这个性质来赋值吗？我们直接把给的数据排序，然后根据中序遍历的顺序进行赋值即可！

代码详解

输入输出前的准备

所需变量：

int N;
int* nums; //用于动态分配掌握全局
int tot = 0;//游标用于赋值
queue<int>Q;//用于层序遍历输出答案
struct node { //每个树的结点(其实也可以设为动态
    int val, l, r;
    node(): val(0), l(-1), r(-1) {}
} Treenode[101];

输入的处理

Input函数

//@输入处理
void Input() {
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; i++) { //由图中可知，这个左右子树编号正好是根据这个序号来给的
        cin >> Treenode[i].l >> Treenode[i].r;
    }
    nums = new int[N];//申请内存存储每个结点的值
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }
    sort(nums, nums + N); //由于我们已经知道二叉搜索树的树形结构，而它的值是遵循中序遍历递增的规律的
}

输出的处理

//@中序赋值
void Inorder(int node) {
    if (node == -1)
        return;
    Inorder(Treenode[node].l);//左子树
    Treenode[node].val = nums[tot++];
    Inorder(Treenode[node].r);//右子树
}

//@BFS打印
void print() {
    Q.push(0);
    while (!Q.empty()) {
        int node = Q.front(); Q.pop();
        if (Treenode[node].l != -1)
            Q.push(Treenode[node].l);
        if (Treenode[node].r != -1)
            Q.push(Treenode[node].r);
        cout << Treenode[node].val;
        if (!Q.empty())
            cout << ' ';
    }
}

整合代码提交

效率还行！

#include <bits/stdc++.h>
using namespace std;
//利用二叉搜索树的性质--中序遍历的序列是递增序列
int N;
int *nums;
int tot = 0;//游标用于赋值
queue<int> Q;//用于最后层序遍历输出答案
struct node {
    int val, l, r;
    node() : val(0), l(-1), r(-1) {}
} Treenode[101];

//@输入处理
void Input() {
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; i++) {//由图中可知，这个左右子树编号正好是根据这个序号来给的
        cin >> Treenode[i].l >> Treenode[i].r;
    }
    nums = new int[N];//申请内存存储每个结点的值
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }
    sort(nums, nums + N);//由于我们已经知道二叉搜索树的树形结构，而它的值是遵循中序遍历递增的规律的
}

//@中序赋值
void Inorder(int node) {
    if (node == -1)
        return;
    Inorder(Treenode[node].l);//左子树
    Treenode[node].val = nums[tot++];
    Inorder(Treenode[node].r);//右子树
}

//@BFS打印
void print() {
    Q.push(0);
    while (!Q.empty()) {
        int node = Q.front();
        Q.pop();
        if (Treenode[node].l != -1)
            Q.push(Treenode[node].l);
        if (Treenode[node].r != -1)
            Q.push(Treenode[node].r);
        cout << Treenode[node].val;
        if (!Q.empty())
            cout << ' ';
    }
}

int main() {
    Input();
    Inorder(0);
    print();
    return 0;
}

#include<iostream>
(720)#include<vector>
#include<algorithm>
(831)#include<queue>
using namespace std;
struct bst{
    int val;
    int left;
    int right;
    bst(int v,int l,int r):val(v),left(l),right(r){}
};
bst* BST[101];
queue<int>myQueue;
vector<int>seq;
int index=0;
void MidOrder(int root){
    if(root==-1){return;}
    MidOrder(BST[root]->left);
    BST[root]->val=seq[index++];
    MidOrder(BST[root]->right);
}
void levelOrder(int root){
    if(root==-1){return;}
    bool flag=true;
    myQueue.push(root);
    while(!myQueue.empty()){
        int current=myQueue.front();
        myQueue.pop();
        if(flag){printf("%d",BST[current]->val);flag=false;}
        else{printf(" %d",BST[current]->val);}
        if(BST[current]->left!=-1){myQueue.push(BST[current]->left);}
        if(BST[current]->right!=-1){myQueue.push(BST[current]->right);}
    }
}
int main(){
    int n;
    cin>>n;
    int leftC,rightC;
   for(int i=0;i<n;i++){
       cin>>leftC>>rightC;
       BST[i]=new bst(0,leftC,rightC);
   }
    int key;
    while(n--){
        cin>>key;
        seq.push_back(key);
    }
    sort(seq.begin(),seq.end());
    MidOrder(0);
    levelOrder(0);
}

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int n = sc.nextInt();
    static Node[] node = new Node[n];
    static StringBuilder builder = new StringBuilder();

    public static class Node {
        int val;
        int left;
        int right;

        public Node(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {


        for (int i = 0; i < n; i++) {
            int left = sc.nextInt();
            int right = sc.nextInt();
            node[i] = new Node(left, right);
        }
        int[] datas = new int[n];
        for (int i = 0; i < n; i++) {
            datas[i] = sc.nextInt();
        }
        
        //二叉搜索树中序遍历就是从小到大排序
        Arrays.sort(datas);
        Assignment(0, datas, 0);

        Queue<Node> queue = new ArrayDeque<>();
        queue.add(node[0]);
        Output(queue);
        System.out.println(builder.substring(0,builder.length()-1));
    }

    private static void Output(Queue<Node> queue) {
        Node node1 = queue.poll();
        builder.append(node1.val + " ");
        if (node1.left != -1) {
            queue.add(node[node1.left]);
        }
        if (node1.right != -1) {
            queue.add(node[node1.right]);
        }
        if (!queue.isEmpty()) {
            Output(queue);
        }
    }
    
    //左根右的赋值,构造二叉搜索树
    private static int Assignment(int key, int[] datas, int index) {
        if (node[key].left != -1)
            index = Assignment(node[key].left, datas, index);
        node[key].val = datas[index++];
        if (node[key].right != -1)
            index = Assignment(node[key].right, datas, index);
        return index;
    }
}

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int lch[100], rch[100], values[100], nodes[100];
int idx = 0;

void dfs(int x){
    if(lch[x] != -1) dfs(lch[x]);
    nodes[x] = values[idx++];
    if(rch[x] != -1) dfs(rch[x]);
}

int main(void){
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> lch[i] >> rch[i];
    }
    for(int i = 0; i < N; i++){
        cin >> values[i];
    }
    sort(values, values + N);
    dfs(0);
    queue<int> que;
    que.push(0);
    while(!que.empty()){
        int x = que.front(); que.pop();
        if(x == -1) continue;
        if(x != 0) cout << " ";
        cout << nodes[x];
        que.push(lch[x]);
        que.push(rch[x]);
    }
    cout << endl;
}