首页 > 试题广场 >

魔力转圈圈

[编程题]魔力转圈圈
  • 热度指数：831 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

牛牛很喜欢玩二叉树。这天牛能送给了他一个以1为根结点的个结点的二叉树，他想对这个二叉树进行一些加工。

牛牛刚刚学会转圈圈，所以很喜欢旋转。现在他想对这颗二叉树进行m次旋转。

每次旋转牛牛会指定一个结点，并让以这个结点为根的子树中的所有结点的左右儿子互换。

多次操作之后，牛牛希望以中序遍历的方式输出操作完之后的二叉树。
示例1

输入

5,3,[4,3,0,0,0],[2,0,0,5,0],[3,1,5]

输出

[2,3,1,5,4]

说明

最开始1的左儿子为4，右儿子为2
2的左儿子为3.
4的右儿子为5.
第一次操作结点3，结点3没有儿子，所以没有发生变化
第二次操作结点1，结点1的左儿子变为2，右儿子变为4. 
结点4的左儿子变为5，右儿子变为不存在。结点
结点2的左儿子变为不存在，右儿子变成3
第三次操作结点5，结点5没有儿子，不发生变化。
最开始1的左儿子为2，右儿子为4
2的右儿子为3.
4的左儿子为5.
中序遍历结果为[2,3,1,5,4]

备注:
数据保证结点1为根节点
第一个参数n代表树的结点个数
第二个参数m代表需要进行的操作个数
第三个参数l包含n个元素，代表每个结点的左儿子结点。如果为0则代表该点无左儿子
第三个参数r包含n个元素，代表每个结点的右儿子结点。如果为0则代表该点无右儿子
第四个参数k包含m个元素，代表m次操作的结点编号。
算法知识视频讲解
开通博客
头像 一个小小小小萌新
发表于 2021-07-28 11:48:59
/** * 审题：（这个题真的看了好多遍才明白） * 一共三个数组，最后一个数组是指定的结点，前两个数组一个表示左子树，一个表示右子树，怎么看呢？（重点！） * 根结点的值是1，所以，要找左子树，[1-1]得到下标0， * 在左子树的数组找1的左儿子，如示例1 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 AimerAimer
发表于 2021-10-11 23:20:17
题意：         一个以1为根结点的n个结点的二叉树，对这颗二叉树进行m次旋转。         每次旋转会指定一个结点，并让 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-08 16:12:55
思路： 题目的主要信息： 一个二叉树根节点为1，l与r分别记录树的左右子节点，其中第个对应节点为的左右子节点 k数组中记录将要旋转的节点，旋转的时候将其所有子树及其子节点都交换位置 最后输出的数组为二叉树的中序遍历 0表示空节点 方法一：递归具体做法：利用递归的思想，遍历每一个要旋转的节点，将其 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 棒棒糖🍭201906101800876
发表于 2021-10-14 08:53:48
NC543 魔力转圈圈 描述 给你一个二叉树和一个操作序列，要求你根据操作序列对二叉树的某个子树做镜像操作，mmm次操作之后，求得操作后的中序序列。 1. 直接模拟 本题是二叉树镜像的升级, 最暴力的做法是直接按题意模拟，对每个操作执行一遍，再中序遍历。 class Solution { publi 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树
难度：
6条回答 2487浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号