二叉树第k层最后一个结点

二叉树第k层最后一个结点

输入格式:
输入第1行为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列。其中空指针信息用0表示。第2行为一个整数k。

输出格式:
输出为一个整数，表示该二叉树中第k层最后一个结点的值，若不存在则输出0。

输入样例1:

1 2 0 0 3 0 0
1

输出样例1:

3

输入样例2:

1 -2 0 0 3 -1 0 0 -1 0 0
2

输出样例2:

-1

解题思路：这道题不难，主要考察树的层次遍历，不过道题需要保留层数，可以用pair<tree,int>函数记录节点和层数，也可以用结构体代替。层次遍历节点，当节点的层数大于k层时输出。
AC代码：

#include<iostream>
#include<queue>
using namespace std;
typedef struct Node{struct Node *l,*r;int data;
}*tree,node;
int x;
void create(tree &T)
{int c;cin>>c;if(c==0){T=NULL;}else{T=new node;T->data=c;create(T->l);create(T->r);}
}
int ac=0;
void seek(tree T)
{if(T){queue<pair<tree,int> > Q;Q.push(make_pair(T,0));while(!Q.empty()){pair<tree,int> s=Q.front();tree e=s.first;int z=s.second;if(z==x){ac=e->data;}else if(z>x){return ;}Q.pop();if(e->l){Q.push(make_pair(e->l,z+1));}if(e->r){Q.push(make_pair(e->r,z+1));}}}
}
int main()
{tree T;create(T);cin>>x;seek(T);printf("%d",ac);
}