二叉树第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); }

技术
今日推荐
阅读数 170189
阅读数 23
阅读数 5
阅读数 0
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信