华为机试(根据广度优先遍历的结果生成二叉树,再进行遍历)

给定一个以顺序存储结构(按每一层从左到右顺序)存储整数值的完全二叉树序列(最多1000个整数),请找出此完全二叉树的所有非叶子节点部分,然后采用后序遍历的方式将该树的非叶子节点输出。

只有一个节点的树,此节点是根节点,应该被认为是非叶子节点

此完全二叉树并非满二叉树,可能存在倒数第二层出现叶子节点,或者无右叶子的情况

后序遍历的顺序:左-右-根

输入描述:

一个通过空格分隔的整数序列字符串

输出描述:

非叶子部分树结构的后序遍历结果

示例1:

输入

1 2 3 4 5 6 7

输出

2 3 1

说明

找到非叶子部分树结构,然后采用后序遍历输出

#include<stdio.h>

#include<malloc.h>

const int max = 100;

typedef struct node

{

int value;

node*left;

node* right;

};

typedef struct stack

{

int top=-1;

node* nodeList;

};

void pushStack(stack *s,node n)

{

if (s->top >= max - 1)

return;

s->nodeList[++s->top] = n;

}

node* topStack(stack *s)

{

if (s->top < 0)

return NULL;

return &s->nodeList[s->top];

}

node* popStack(stack *s)

{

if (s->top < 0)

return NULL;

return &s->nodeList[s->top--];

}

typedef struct queue

{

stack input;

stack output;

};

void pushQueue(queue *q, node n)

{

pushStack(&q->input, n);

}

node *topQueue(queue *q)

{

if (topStack(&q->output) != NULL)

{

return topStack(&q->output);

}

while (topStack(&q->input)!=NULL)

{

pushStack(&q->output, *popStack(&q->input));

}

return topStack(&q->output);

}

node *popQueue(queue *q)

{

if (topStack(&q->output) != NULL)

{

return popStack(&q->output);

}

while (topStack(&q->input) != NULL)

{

pushStack(&q->output, *popStack(&q->input));

}

return popStack(&q->output);

}

void first(node *n)

{

if (n->value==-1)

return;

printf("%d ", n->value);

first(n->left);

first(n->right);

}

int main()

{

queue q;

q.input.nodeList = (node*)malloc(sizeof(node)*max);

q.output.nodeList = (node*)malloc(sizeof(node)*max);

node root;

root.left = (node*)malloc(sizeof(node));

root.right = (node*)malloc(sizeof(node));

root.value = 1;

int valueList[] = { 1, 2, 3, 4, 5, 6, 7 };

int index = 1;

pushQueue(&q, root);

while (topQueue(&q)!=NULL)

{

node *n= popQueue(&q);

if (index < 7)

{

n->left->value = valueList[index++];

n->left->left = (node*)malloc(sizeof(node));

n->left->right = (node*)malloc(sizeof(node));

pushQueue(&q, *n->left);

}

if (index < 7)

{

n->right->value = valueList[index++];

n->right->left = (node*)malloc(sizeof(node));

n->right->right = (node*)malloc(sizeof(node));

pushQueue(&q, *n->right);

}

if (index>7)

{

//set 尾节点标志位

n->left->value=-1;

n->right->value = -1;

}

if (index == 7)

{

index++;

}

}

//先序变里root 因为对有值的节点的left和right都赋值了,使用结尾的节点4 5 6 7的left right都不为NULL 在遍历的时候注意一下

first(&root);

}

全部评论
这题测试用例是不是有问题。我是拿数组做的。首先收集所有的非叶子节点:如果i**2在节点数组中,当前节点i为根节点,加入根节点集。在根节点集中,从节点0开始递归显示,print(左节点) print(右节点) print(当前节点)。自测了几个数据没问题,提交了就是死活通不过。
点赞 回复 分享
发布于 2023-08-27 16:49 广东
我这个结果不对,我是先序遍历的,也没去截掉不需要的部分,懒得改了,凑合看吧
点赞 回复 分享
发布于 2023-06-25 19:35 浙江
主要是c语言没有队列要自己实现比较麻烦,要是其他语言会简单很多。。。。***
点赞 回复 分享
发布于 2023-06-25 19:33 浙江

相关推荐

真的很糟糕:欲哭无泪
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
07-04 09:21
已编辑
Java
推拿大师:这是hr发的钓鱼贴吗
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务