泛型树中下一个较大的元素

Question

我正在尝试解决这个代码挑战:

在给定树的根和整数n的情况下，查找并返回泛型树中下一个较大的节点。

输入格式第一行输入包含树的节点的数据，以级别顺序的形式。为根节点的顺序是:数据,根节点的儿童数量,每个子节点的数据并为每个节点等等。树节点的数据用空格分隔。下面一行包含一个整数，表示n的值。

例子样本输入:

10 3 20 30 40 2 40 50 0 0 0 0
21

样本输出:

30

后端已经将输入转换为具有data和children属性的树。根节点和n的值作为参数传递给函数。

我决定将所有节点及其数据存储到一个列表中。下面是我的代码:

def nextLargest(tree, n):
li=[]

def helper(tree):
li.append([tree,tree.data])
for child in tree.children:
helper(child, n)
li=sorted(li,key=lambda x: x[1])

for ele in li:
if ele[1] > n:
return ele[0]

但是它不起作用:append方法不起作用，因为列表总是空的。是因为我在存储地址吗?我的代码中的问题在哪里?

我知道这不是解决它的最好方法，但我有点好奇如何解决它。

Answer 1

问题是没有调用helper。你需要做的是:

helper(tree)
li=sorted(li,key=lambda x: x[1])

helper的递归调用有第二个不应该在那里的参数。应该是:

for child in tree.children:
helper(child)

通过这些更改，函数将返回下一个最大的节点(如果有的话)。如果您需要打印结果，不要忘记它是一个节点实例，您需要获取它的数据。

优化空间不需要使用O(n)辅助空格。尝试在不将节点存储在列表中的情况下执行此操作。例如，您可以使用生成器遍历节点。

这是一个剧透解决方案:

def walk(tree): yield tree for child in tree.children: yield from walk(child) def nextLargest(tree, n): return min(((node.data, i, node) for i, node in enumerate(walk(tree)) if node.data > n), default=(0, 0, None))[2]