最短根到叶路径

Question

在 BST（二叉搜索树）中查找最短根到叶路径的最简单方法是什么（最好使用递归）。 首选Java，伪代码也可以。

谢谢！

Answer 1

一般描述：

使用广度优先搜索 (BFS)与深度优先搜索 (DFS) 相反。 找到第一个没有子节点的节点。

使用 DFS，您可能会在某些输入树上幸运（但无法知道您是否幸运，因此您仍然需要搜索整个树），但使用 BFS 方法要快得多，并且您可以找到解决方案，而无需触及所有树节点。

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

伪代码：

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

1. 将根节点放入队列中。

当队列不为空且未找到结果时重复：

2. 从队列开头拉出一个节点并检查它是否没有子节点。 如果它没有孩子你
   完成后，您找到了最短路径。
3. 否则将所有子级（左、右）推入队列。

查找所有最短路径：

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

替代方案：

如果您决定使用 DFS，则必须搜索整个树才能找到最短路径。 但这可以通过保留迄今为止最短的值并仅检查未来节点的深度直到找到新的最短值或直到达到迄今为止的最短值来优化。 不过，BFS 是一个更好的解决方案。

Answer 2

这是用 C++ 编写的，但它非常简单，您可以轻松转换它。 只需将 min 更改为 max 即可获得最大树深度。

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

只是为了解释一下它在做什么，它从叶节点开始计数（当找到叶节点时返回 0），然后向上计数到根。 对树的左侧和右侧执行此操作并取最小值将为您提供最短路径。

Answer 3

就访问的顶点数量而言，广度优先搜索完全是最优的。 您必须访问在广度优先搜索中访问的每个顶点，只是为了证明您拥有最近的叶子！

但是，如果您必须使用递归，那么 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 

Answer 4

static int findCheapestPathSimple(TreeNode root){

if(root==null){
    return 0; 
}

return root.data+Math.min(findCheapestPathSimple(root.left), findCheapestPathSimple(root.right));

}

Answer 5

shortestPath(X)
if X == NIL
    return 0
else if X.left == NIL and X.right == NIL //X is a leaf
    return 1
else
    if X.left == NIL
        return 1 + shortestPath(X.right)
    else if X.right == NIL
        return 1 + shortestPath(X.left)
    else
        return 1 + min(shortestPath(X.left), shortestPath(X.right))