二叉树方法

Question

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

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

我已经写了我的代码，它应该工作得很好，但只有一个问题。因为我必须递归地执行它，所以我必须自己调用函数，这意味着列表的初始化将再次发生，并且只会重置列表。这不是我想要的。我想继续将元素添加到这些名单，并最终返回它们...

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

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) 

Answer 1

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

这被称为递归步骤，只要递归的基础（即使递归停止的规则）是正确的，它就起作用。

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关键字将全局值绑定到局部变量来在代码中执行此操作。

Answer 2

在某种程度上，你应该确保初始化只发生一次。有不同的做法。

做，就做初始化你的函数之外的一种方式，让我们假设你有这样的事情（伪代码）：这样做是

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() 

另一个简单的（但不一定是漂亮的方式）

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已经完成，比如这样的事情之外，一些全局变量设置为true。我肯定会尝试在函数外部使用init的东西。希望这能为你解决。