#g6004. [GESP6级模拟题]图书管理
[GESP6级模拟题]图书管理
题目背景
学校图书馆的图书采用了一套"二叉树分类系统"对图书进行管理。
所有图书的分类编号规则如下:
- 根类别编号为 ,
- 若某个类别的编号为 ,则它的左子类别编号为 ,右子类别编号为 。
这样,每一本书的分类编号就对应了二叉树中的一个节点。
例如,编号为 的图书,其分类路径为:,即根类别下的右子类()再向右子类()。
现在,管理老师想快速了解任意两个图书类别之间"隔了多少层"。
题目描述
给定两个图书的分类编号 和 ,求它们之间的距离。
距离定义为:在分类二叉树中,从一个节点走到另一个节点所需经过的最少边数。
输入格式
一行,两个正整数 ,表示两个图书的分类编号。
输出格式
输出一个整数,表示 和 之间的距离。
样例输入
5 6
样例输出
4
样例解释
分类二叉树的结构如下(只画出部分):
1
/ \
2 3
/ \ / \
4 5 6 7
- 从 到 的最短路径为:,共 条边。
数据范围