二叉树算法题 最小距离

来源：百度知道 编辑：UC知道 时间：2024/07/02 11:20:57
请设计一种方法，找出给定二叉树中任意两个结点之间的最小距离。二叉树两个结点间的最小距离定义为：这两个结点的最近公共祖先结点分别到这两个结点的路径长度之和。

我想到可以用广度优先遍历，相当于看做是完全二叉树来编号，而得两个结点的号之后，可以仅用编号算出最短路径长。可是总觉得实现起来有些困难……
如果用递归的中序的话，好像很容易算乱……
求高手指点~
多谢了~~~
希望回答详细些~

我觉得用深度优先好。在第几层为根的时候能同时找到这里俩，问题就结了。每条路的长度就是你相对遍历深度，两个相对遍历深度之和就是距离。

还有骗子抢沙发……