最简单的方法(最好是使用递归)是在BST(二进制搜索树)中找到最短的根到叶路径的方法。 Java更喜欢伪代码，可以。

谢谢！

解决方案

概述：

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

使用DFS可能会在某些输入树上很幸运(但是无法得知我们很幸运，因此我们仍然需要搜索整棵树)，但是使用BFS方法的速度要快得多，我们无需动手就能找到解决方案节点。

要找到从根到叶的路径，可以使用父引用一直沿第一个找到的无子节点一直追溯到根。如果每个节点中都没有存储父级引用，则在递归时可以跟踪父级节点。如果列表顺序相反，则可以将其全部压入堆栈，然后将其弹出。

伪代码：

问题很简单。这是找到最小长度的伪代码：

• 将根节点放在队列中。

在队列不为空时重复此操作，但未找到结果：

• 从队列的开头拉节点，然后检查它是否没有子节点。如果没有孩子，那么我们找到了最短路径。
• 否则，将所有子级(左，右)推入队列。

查找所有最短路径：

要查找所有最短路径，我们可以将节点的深度以及队列内的节点一起存储。然后，我们将继续对队列中具有相同深度的所有节点执行该算法。

选择：

相反，如果我们决定使用DFS，则必须搜索整个树以找到最短路径。但是，可以通过保留到目前为止最短的值，并仅检查将来节点的深度，直到找到新的最短的节点，或者直到达到最短的节点为止，才能对此进行优化。 BFS是一个更好的解决方案。

这是用C ++编写的，但是它是如此简单，我们可以轻松地对其进行转换。只需将min更改为max即可获得最大树深。

int TreeDepth(Node* p)
{
    return (p == NULL) ? 0 : min(TreeDepth(p->LeftChild), TreeDepth(p->RightChild)) + 1;
}

只是为了解释它在做什么，它从叶子节点开始计数(找到叶子时返回0)并向上计数到根。在树的左侧和右侧进行此操作，并采取最小的操作，将为我们提供最短的路径。

就访问的顶点数而言，广度优先搜索是最佳的。我们必须在广度优先搜索中访问要访问的每个顶点，以证明我们拥有最近的叶子！

但是，如果我们有权使用递归，则Mike Thompson的方法几乎是正确的方法，并且稍微简单一些。

TD(p) is
  0 if p is NULL (empty tree special case)
  1 if p is a leaf (p->left == NULL and p->right == NULL)
  min(TD(p->left), TD(p->right)) if p is not a leaf