1 条题解
-
0
Guest LV 0 MOD
-
1
这个题作为普及/提高- 难度并不大
可以先把这道题分解成个小问题:
:求二叉树的深度
:求二叉树的宽度
:求给定两个结点间距离
先来解决第一个问题:求深度
这个问题很好解决
每一个子结点的深度都是它父亲节点的深度(一号结点的深度是)
这个部分很好理解;接下来上这一部分的代码:
然后来解决第二个问题:求宽度
同样,这个问题很好解决
刚才求过了每一个深度都有几个结点()
所以思路也很明确了
上代码:
接着,就是本题的的重头戏:求给定两个结点间距离
思路一(本思路有误):
分别求出两个结点与号结点的深度差
思路二(正确思路):
求两个结点的最近公共祖先
求 的方法应是树上倍增
但是这题数据太小了,所以我就用暴力来求解:
最后,贴上AC代码:
- 1