设一颗根节点为$1$的二叉树有若干个节点，已知其左右儿子，并预留其“兄弟”节点（深度相同的节点中距离该节点最近的右侧节点）的空间。

（节点的兄弟节点事先未知）

例：

        1
     2     3
  4      5   6
7              8

满足：

（再次强调，节点的兄弟节点事先未知）

要求：不使用除树左右兄弟节点外超过$O(1)$级别的空间（即不得另外使用队列、数组、std::vector等），求出该二叉树的bfs序。就本例子而言，输出应为：

1 2 3 4 5 6 7 8

本萌新尝试写dfs，然而并不能准确的求出各节点的兄弟节点，故此求大佬支援；以下是写废了的代码片段，供大佬们参考。

struct tree{
    int lson,rson,brother;
}tree[100];
  
int head[100];

int sons(int node){ //如果左右儿子均为空，否则返回0；如果有儿子，优先返回左儿子，次者返回右儿子
    if(tree[cur].lson==0 && tree[cur].rson==0) return 0;
    if(tree[cur].lson) {
        return tree[cur].lson;
    }
    return tree[cur].rson;
}

void dfs1(int cur){ //dfs1 finds the brother
    if(tree[cur].lson==0 && tree[cur].rson==0) return;
    if(tree[cur].lson!=0 && tree[cur].rson!=0) tree[tree[cur].lson].brother=tree[cur].rson;
    if(tree[cur].lson!=0 && tree[cur].rson==0){
        int temp=cur;
        while(temp!=0 && tree[tree[cur].lson].brother==0){
            tree[tree[cur].lson].brother = sons(tree[tree[temp].brother]);
            temp=tree[temp].brother;
        }
    }
    if(tree[cur].lson==0 && tree[cur].rson!=0){
        int temp=cur;
        while(temp!=0 && tree[tree[cur].rson].brother==0){
            tree[tree[cur].rson].brother = sons(tree[tree[temp].brother]);
            temp=tree[temp].brother;
        }
    }
    if(tree[cur].lson) dfs1(tree[cur].lson);
    if(tree[cur].rson) dfs1(tree[cur].rson);
}

void dfs2(int cur){
    int firstSon,flag=0; //This denotes the first node in the layer to have a son; the flag helps prevent further edits
    int curNode=cur;
    while(curNode!=0){
        printf("%d ",curNode);
        if((tree[curNode].lson || tree[curNode].rson) && flag==0) {
            firstSon=curNode;
            flag=1;
        }
        curNode=tree[curNode].brother;
    }
    printf("\n");
    if(flag==0) return;
    if(tree[firstSon].lson){
        dfs2(tree[firstSon].lson);
    }
    else{
        dfs2(tree[firstSon].rson);
    }
}


dfs1(1);
dfs2(1);