获取节点，并根据用户的特定输入进行分组。

Question

我有一棵二进制树。每个节点都是一个结构体，有2个值：宽度和长度，用户的输入是根据一个或两个标准（高度，宽度）对它们进行分组。

用户的输入是根据一个或两个标准(高度，宽度)对它们进行分组.对于这种分组，只考虑叶子节点.考虑附图中的树。如果用户说基于长度进行分组，结果是[8,5,7]，因为它的长度是20，[9,6]，因为它的长度是10。

如果用户说基于长度和宽度的组，那么输出结果将是[8,5]。w=20,l=30 , [9,6] l=10，w=20 , [7] 长=20，宽=10 .

我处理这个问题的方法是遍历树两次，收集2个 "list of lists"，然后处理得到一个新的 "list of lists"，将唯一的l&w值分组在一起。

用户还可以选择给出级别作为输入。如果把级别作为输入，那么同样的步骤就会发生在这个级别上，而不是叶子节点上。

有没有比我提到的更好的方法？我正在用C++编写这段代码。

Answer 1

数据。

构造一个带字段的对象列表

• 长度
• 宽度
• 层次

您可以通过进行级别顺序遍历来创建这个 "主 "列表。

并从主列表中构造以下列表。

• a length-level-sorted list : 首先按长度排序，然后按级别排序的列表。

• 宽度-等级排序列表：先按宽度排序，再按等级排序的列表。

• a length-width-level-sorted list : 先按长度，再按宽度，再按级别排序的列表。

查询( log n )。

• 对于长度查询：在长度级排序的列表上进行二进制搜索，并查找找到的索引左边和右边索引的所有对象，并返回该组--应该是。O(log(n))

• 对于宽度查询：在宽度级排序的列表上做同样的操作--应该是在宽度级排序的列表上做同样的操作。O(log(n))

• 对于长度和宽度的查询：在长度-宽度级别-排序的列表上先按长度，再按宽度进行二元搜索--应该为 O(log(n))

• 对于级别选项：如果在上述任何一个查询中，级别被包含在查询中--只需按级别进行二进制搜索--应该是。O(log(n)) 再次。