©2020-2024 ioDraw All rights reserved,
Privacy Policy
二叉树第k层最后一个结点 (10 分)
给定一棵非空二叉树，其结点的数据域为不等于0的整数，请编写程序输出该二叉树中第k层最后一个结点的值，若不存在则输出0。
输入格式:
输入第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); }