最短的根到叶子路径

Question

什么是最简单的方法,最好是使用递归,在BST(二进制搜索树)中找到最短的根到叶路径.Java首选,伪代码没关系.

谢谢!

Answer 1

一般说明:

使用广度优先搜索(BFS)而不是深度优先搜索(DFS).找到没有子节点的第一个节点.

使用DFS你可能会对一些输入树感到幸运(但是没有办法知道你很幸运,所以你仍然需要搜索整个树),但使用BFS方法要快得多,你可以找到一个解决方案而不需要全部节点.

要查找根到叶子路径,您可以使用父引用跟随第一个找到的无子节点一直返回到根.如果每个节点中都没有存储父引用,则可以在递归时跟踪父节点.如果您的列表顺序相反,则可以将其全部放在堆栈中然后将其弹出.

伪代码:

问题很简单; 这里是伪代码,以找到最小的长度:

1. 将根节点放在队列中.

在队列不为空时重复,但未找到任何结果:

2. 从队列的开头拉一个节点,检查它是否没有子节点.如果它没有孩子你完成了你找到了最短的路径.
3. 否则将所有孩子(左,右)推入队列.

找到所有最短路径:

要查找所有最短路径,您可以将节点的深度与节点内的节点一起存储.然后,您将继续使用相同深度的队列中所有节点的算法.

替代方案:

如果您决定使用DFS,则必须搜索整个树以找到最短路径.但是这可以通过保持目前为止最短的值来优化,并且只检查未来节点的深度,直到找到新的最短节点,或直到达到目前为止最短的节点.BFS是一个更好的解决方案.