php - 如何在不使用广度优先遍历的情况下找到二叉树第 k 层的节点数？

Question

给定这个二叉树(实际上，二叉树可以是随机的和动态的，这只是一个例子...):

请参阅二叉 TreeMap 像的链接:binary tree example

这是给定的事实:

1. 所有节点都连接到它们的父节点，这样我们就可以从下到上遍历(当然也可以从上到下遍历)。
2. 所有节点都保存关于它们的左右部分有多少个后代的信息。

问题是这样的:我需要找到一种方法来计算第 2 层中的节点总数(实际上，在任何层中，但现在，让我们专注于第 2 层)。显然，如果我们事先知道二叉树的结构，答案是 3，但假设我们没有这张图片，只有给定的事实。

这里的另一个问题是我们将从第 2 层(我们的目标层)中的节点开始，而不是根节点。在此示例中，我选择了节点 F。

我知道使用广度优先顺序遍历是直接的解决方案，但我发现它太耗时了，因为每次我读取一个节点时，我都会从数据库中查询它。

我正在寻找更实用的方法。但是如果由于给定数据不足而“不可能”解决这个问题，请告诉我应该提供哪些其他数据才能解决这个问题。我会评估它是否可行。

顺便说一句，我正在创建一个网站并使用 PHP 和 MySQL。但我只想要解决方案的概念或解释，更像是一种算法而不是编程片段或代码...

希望有人能回答我...非常感谢!

Answer 1

“广度优先搜索”是一种方法。但是，如果您不想使用它，我建议您在节点中包含指向兄弟的指针。如果您通常必须执行此类查询，那将是一个很大的节省。

编辑:

如果您可以对节点进行非规范化，并将所有节点的同级和级别存储在表中，那么您就可以毫无问题地进行查询。

SELECT * FROM nodes where level=2