1

我正在尝试编写一个函数，该函数返回二叉树的叶节点列表和内部节点列表的元组。

所以我尝试这样做的方式是初始化两个列表（一个用于叶节点，另一个用于内部节点）。

我已经编写了我的代码，它应该可以正常工作，但只有一个问题。由于我必须递归地执行此操作，因此我必须调用该函数本身，这意味着列表的初始化将再次发生，并且只会重置列表。这不是我想要的。我想继续向这些列表中添加元素并最终返回它们......

编辑：对不起，我不能添加我的代码，但我可以给你一个粗略的想法：

list1=[]
list2=[]
if (leaf node reached):
            add leaf node to list1

else:
            add node to list2
            call the function on the left child
            call the function on the right child
return (leaves_data,internals_data)
4

2 回答 2

0

在某种程度上，您应该确保初始化只发生一次。有不同的方法可以做到这一点。

一种方法是在函数之外进行初始化，假设你有这样的东西（伪代码）：

function recursiveFunction():
    // Here you had your old init code, you don't need it here anymore
    // Here your function is the same as before
    // [ ... ]
    recursiveFunction()
    return; // Some return statement
end 

// Init stuff here (make sure these variables/list you init are globally defined, so they can be accessed from inside the function
// Then call your recursive function:
recursiveFunction()

另一种简单（但不一定很漂亮）的方法是在初始化完成后将一些全局变量设置为 true，例如：

global variable init_is_done = false // Make sure this can be accessed inside your function

function recursiveFunction():
    // Check if init_is_done is true before doing init
    if not init_is_done:
        // Have your init code here
        init_is_done = true
    endif

    // Here your function is the same as before
    // [ ... ]
    recursiveFunction()
    return; // Some return statement
end 

// Now you can just call your function
recursiveFunction()

根据您使用的语言，不同的方法可能会很好。我当然会尝试将 init 东西放在函数之外。希望这对你有用。

于 2013-03-15T02:37:02.730 回答
0

在每个递归步骤中，您最初都会创建一个空列表来仅存储来自该迭代的数据。然后调用递归函数，该函数有望返回具有更多内容的其他列表。您将返回的列表附加到您的列表中，并且您将在递归函数正在迭代的树的相关分支中获得正确的部分结果。最后，您从函数返回合并列表，允许树的上层再次追加结果并增长结果，直到它返回到根级别。

这称为递归步骤，只要递归的基础（即使递归停止的规则）正确，它就可以工作。

def get_nodes(l):
    # Recursion base
    if l is None: return ([], [])
    if l.children is None: return ([], [l])

    # Recursion step
    this = ([l], [])
    internal, leaf = get_nodes(l.children.left)
    this[0] += internal
    this[1] += leaf

    internal, leaf = get_nodes(l.children.right)
    this[0] += internal
    this[1] += leaf

    return this

（注：未经测试的伪代码，只是一个例子）

上面的所有描述都是概念性的，应该被认为是微不足道的实现。但是，在实际实现中，您将避免多次创建和附加多个列表。您可以通过将列表移动到全局范围并使用 global 关键字将全局值绑定到局部变量来在代码中执行此操作。

于 2013-03-15T02:47:00.883 回答