编程题
### 问题描述 卓卓最近在学习二叉树,她了解到二叉树的概念,于是想到了一个问题,希望你帮她解答。 卓卓给定一棵二叉树,想要求出该二叉树的深度、宽度及结点间的距离,其中深度表示这棵树的层数,宽度表示二叉树上同一层最多的结点个数,结点 $u, v$ 之间的距离表示从 $u$ 到 $v$ 的最短有向路径上向根结点的边数加上向叶结点的边数的两倍。 如图所示的一棵二叉树: ![二叉树](https://dn-simplecloud.shiyanlou.com/questions/uid2002922-20231017-1697554807603) - 深度:$3$。 - 宽度:$2$。 - 结点 $2$ 和 $5$ 之间的距离:$3$。 - 结点 $2$ 和 $4$ 之间的距离:$4$。 给定一棵以 $1$ 号结点为根的二叉树,请求出其深度、宽度和两个指定结点 $x, y$ 之间的距离。 ### 输入格式 第 $1$ 行输入 $1$ 个正整数,表示树的结点个数 $n$。 接下来 $n - 1$ 行,每行两个正整数 $u, v$,表示树上存在一条连接 $u, v$ 的边,且 $u$ 是 $v$ 的父结点,$v$ 是 $u$ 的子结点。 最后一行输入两个正整数 $x, y$,表示求解 $x, y$ 之间的距离。 ### 输出格式 输出三行,每行一个正整数,依次表示二叉树的深度、宽度和 $x, y$ 之间的距离。 ### 样例输入 ```plaintext 5 1 3 1 4 3 2 3 5 2 5 ``` ### 样例输出 ```plaintext 3 2 3 ``` ### 评测数据规模 数据保证:$1 \leq u, v, x, y, \leq n \leq 100$,且给出的保证是一棵二叉树。
查看答案
赣ICP备20007335号-2