首页 > 试题广场 >

一棵二叉树现有如下关系：若任意父结点为(x,y)，那么其左子

[单选题]
一棵二叉树现有如下关系：若任意父结点为(x,y)，那么其左子结点为(x + y,y)，右子结点为(x,y + x)。已知一棵二叉树根结点为(1,1)，请问以下哪个结点可能存在于该树中？ 
  • (88,75)
  • (76,128)
  • (87,93)
  • (106,72)
查看正确选项
添加回答
い王小喵头像 い王小喵
按题目规律从下往上推父节点一直推到根节点是（1，1）就是对的 A    （88，75）——（13，75）——（13，62）——（13，49）——（13，36）——（13，23）——（13，10）——（3，10）——（3, 7）——（3，4）——（3，1）——(2，1) ——(1，1) 是对的 B     （76，128）——（76，52）——（24，52）——（24，28）——（24，4）——（20，4）——（16，4）——（12，4）——（8，4）——（4，4）——（0，4）/（4，0） 错的 C D同上
发表于 2019-04-07 02:30:06 回复(1)
许愿多多涨薪头像 许愿多多涨薪
这不就是辗转相减法求最大公约数嘛
换个方法求最大公约数为1就可以了
发表于 2020-11-13 13:19:16 回复(0)
T.S-繁头像 T.S-繁
gcd(a,b)=gcd(a,a+b) 所以这题只要找到互质的两个数就行了，或者也可以逆向求出每个点对应的根节点，计算方法等价于gcd
发表于 2022-09-04 18:16:56 回复(0)
emcpper头像 emcpper

maxx - y = px, y = py

maxy - x = py, x = px


88 - 75 = 13

75 - (75/13 * 13) = 10

13 - 10 = 3

10 - (10/3 * 3) = 1

选A


128 - 76 = 52

76 - 52 = 24

52 - 48 = 4

48 % 4 == 0


93 - 87 = 6

87 - (87/6*6) = 3

6 % 3 == 0


106 - 72 = 34

72 - 68 = 4

34 - (34/4*4) = 2

4 % 2 == 0

发表于 2019-08-05 23:02:20 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 吉比特 2018 PHP工程师 Java工程师
上传者：小小
难度：
4条回答 909浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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