九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1541-九度Online Judge,用代码记录你的成长之路!

题目1541:二叉树

时间限制:1 秒

内存限制:128 兆

特殊判题:

提交:425

解决:81

题目描述:

旋转是二叉树的基本操作,我们可以对任意一个存在父亲节点的子节点进行旋转,包括如下几种形式(设被旋转节点为x,其父亲节点为p):
1.左旋
旋转前,x是p的右儿子。
x的左儿子(若存在)变为p的右儿子,p变为x的左儿子。如下图

2.右旋
旋转前,x是p的左儿子。
x的右儿子(若存在)变为p的左儿子,p变为x的右儿子。如下图

综上,我们可以通过检查选择前x是p的左儿子还是右儿子来判断该次旋转是左旋还是右旋。

给定一颗n个节点的二叉树,其节点由1至n编号,并给定一系列操作,如下:
1.rotate x,对编号x的节点进行旋转,若x为根节点,则不进行任何操作。
2.parent x,输出编号x的父亲节点编号,若x为根节点输出-1。
3.size x,输出以x为根节点的子树的节点个数。

输入:

输入包含多组测试用例。
每组测试用例开头为一个整数n(1<=n<=1000),代表二叉树的节点个数。
接下去n行描述,二叉树原始的状态,第i行为两个整数x,y,代表i号节点的左儿子节点为x号节点,右儿子节点为y号节点,若x或y为-1,则表示相应儿子节点不存在。编号的范围为1到n。
接下去一行为一个整数t(1<=t<=50000),代表操作的个数。
最后t行,每行代表一个对二叉树的操作,描述如上所示。

输出:

对于每组测试用例,输出操作parent x和size x查询的数据。

样例输入:
5
2 3
-1 -1
4 5
-1 -1
-1 -1
5
size 1
rotate 5
size 5
parent 3
parent 4
样例输出:
5
3
5
3