最短的根到叶子路径

Question

最简单的方法是使用递归，在BST（二进制搜索树）中找到最短的根到叶路径。 Java首选，伪代码没关系。

谢谢！

Answer 1

一般说明：

使用广度优先搜索（BFS）而非深度优先搜索（DFS）。找到没有子节点的第一个节点。

使用DFS你可能会对一些输入树感到幸运（但是没有办法知道你很幸运，所以你仍然需要搜索整个树），但使用BFS方法要快得多，你可以找到解决方案没有触及所有节点。

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

<强>的伪代码：

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

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

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

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

查找所有最短路径：

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

<强>替代：

如果您决定使用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));

}