题目就是给出一棵二叉搜索树，已知根节点为0，并且给出一个序列要插入到这课二叉树中，求这棵二叉树层次遍历后的序列。

　　用结构体建立节点，val表示该节点存储的值，left指向左孩子，right指向右孩子。中序遍历的顺序正好是序列从小到大的顺序，因此中序遍历的时候顺便赋值就可以了，最后层次遍历输出。

思路一：中序遍历的时候赋值

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define LEFT 0#define RIGHT 1using namespace std;const int maxn=105;int cnt=0;/*中序遍历的顺序即为序列从小到大的顺序，因此中序遍历的时候顺便赋值，最后层次遍历输出即可。*/struct Node{    int val;    int left;    int right;}node[maxn];void dfs(int i,int*a){    if(i==-1)        return;    dfs(node[i].left,a);    node[i].val=a[cnt];    cnt++;    dfs(node[i].right,a);}int main(){    int n,l,r;    int a[maxn];    scanf("%d",&n);    for(int i=0;i
           
            q; q.push(node[0]); bool first=true; while(!q.empty()){ Node tmp=q.front(); q.pop(); if(first){ printf("%d",tmp.val); first=false; } else{ printf(" %d",tmp.val); } if(tmp.left!=-1) q.push(node[tmp.left]); if(tmp.right!=-1) q.push(node[tmp.right]); } return 0;}
           
          
         
        
       
      

 

 

思路二：两次dfs

　　这是我最开始的解题思路，复杂化了，不过好歹一次就AC了。

　　节点leftnum存储它的左子树的节点个数，rightnum存储它的右子树的节点个数，num存储以该节点为根节点的子树的节点个数。smallernum则是存储值比它小的节点个数。id代表了该节点是其父亲节点的左孩子还是右孩子，father是其父节点。

　　这样我们就能根据smallernum来判断该节点在序列（从小到大排列）中的位置。

　　第一次dfs把leftnum、rightnum、num给求出来。

　　第二次dfs则是计算smallernum，这里要分两种情况来考虑。

　　1.节点i为左孩子

　　　　那么往上追溯祖先节点，直到第一个id为右孩子的节点p，那么节点i的smallernum则为：

　　　　p的父亲节点的smallernum+1（即p的父亲节点）+节点i的左子树个数

　　2.节点i为右孩子

　　　　那么节点i的smallernum则为：

　　　　其父亲节点的smallernum+1（其父亲节点）+节点i的左子树个数。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define LEFT 0#define RIGHT 1using namespace std;const int maxn=105;struct Node{    int id;    int val;    int father;    int left;    int right;    int leftnum; //the number of left subtree    int rightnum;    int smallernum; //the number of left nodes,not only left subtree.    int num; //the number of this subtree}node[maxn];/*calculate leftnum and num*/int dfsNum(int i){    if(i==-1)        return 0;    int l=node[i].left;    int r=node[i].right;    if(i==0){        node[i].id=LEFT;        node[i].father=-1;    }    if(l!=-1){        node[l].id=LEFT;        node[l].father=i;    }    if(r!=-1){        node[r].id=RIGHT;        node[r].father=i;    }    node[i].leftnum=dfsNum(l);    node[i].rightnum=dfsNum(r);    node[i].num=node[i].leftnum+node[i].rightnum+1;    return node[i].num;}void dfsSmallerNum(int i){    if(i==-1)        return ;    int l=node[i].left;    int r=node[i].right;    dfsSmallerNum(l);    node[i].smallernum=0;    if(node[i].id==LEFT){        int p=node[i].father;        while(p!=-1){            if(node[p].id==RIGHT)                break;            p=node[p].father;        }        if(l!=-1)            node[i].smallernum+=node[l].num;        if(p>0){            node[i].smallernum+=node[node[p].father].smallernum+1;        }    }    else{        if(l!=-1)            node[i].smallernum+=node[l].num;        if(i>0)            node[i].smallernum+=node[node[i].father].smallernum+1;    }    dfsSmallerNum(r);}int main(){    int n,l,r;    int a[maxn];    scanf("%d",&n);    for(int i=0;i
           
            q; q.push(node[0]); bool first=true; while(!q.empty()){ Node tmp=q.front(); q.pop(); if(first){ printf("%d",tmp.val); first=false; } else{ printf(" %d",tmp.val); } if(tmp.left!=-1) q.push(node[tmp.left]); if(tmp.right!=-1) q.push(node[tmp.right]); } return 0;}