13

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

谢谢！

4

5 回答 5

16

一般说明：

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

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

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

伪代码：

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

  1. 将根节点放入队列。

在队列不为空时重复，没有找到结果：

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

查找所有最短路径：

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

选择：

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

于 2008-09-22T01:12:44.577 回答
2

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

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

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

于 2008-09-22T01:15:34.367 回答
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
于 2008-09-22T02:24:09.100 回答
0

静态 int findCheapestPathSimple(TreeNode root){

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

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

}

于 2017-01-06T10:36:35.163 回答
0 
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))
于 2021-10-01T04:52:34.343 回答