计算树中的叶节点

Question

假设我们有一棵树，其中每个节点都有预先确定的传出节点集。有没有可能想出一种快速的方法/优化来计算给定级别值的叶节点的数量？如果有人能提出任何想法/链接/资源来做同样的事情，那就太好了。

Answer 1

不是的。你仍然需要遍历整棵树。仅通过树的每个节点的子节点的数量无法预测或近似精确的结构。

除此之外:只需保留一个计数器，并在每次插入时更新它。简单得多，不会改变任何操作的时间复杂度，除了计算叶子，这将减少到O(1)。

Answer 2

这实际上可能是非常困难的事情。由于它不同的是什么是编程语言，什么是输入数据结构，都是树的二进制或一般树(子树的任意数量)，树的大小。

最一般的想法是从根开始运行DFS或BFS，以获取每个节点级别，然后创建一个集合列表，其中每个集合包含单个级别的节点。集合可以是任何结构，标准列表就可以了。

假设你正在使用C++，如果你需要性能(甚至比C更好)，这是很好的，如果不是最好的实用选择的话。

假设我们有一个通用的树，输入结构是你提到的邻接表。

//nodes are numbered from zero to N-1
vector<vector<int>> adjList;

然后，您可以运行BFS或DFS，这两种方法都适用于树，为每个节点保留一个级别。下一个节点的级别是它的父节点的级别加1。

一旦发现了级别，就可以像这样放入节点。

vector<vector<int>> nodesPartitionedByLevels(nodeCount);
//run bfs here
//inside it you call
nodesPartitionedByLevels[level].push_back(node)

事情就是这样。

然后，当您有了级别时，您将迭代该级别上的所有节点，并检查邻接列表是否与任何节点竞争。

基本上，您调用adjList[node].empty()。如果为真，则为叶节点。