python - 如何递归地将斐波那契数列插入二叉树

Question

希望有人能提供帮助，我不是程序员，但一直对探索斐波那契数列及其递归树感兴趣...

我已经创建了一个二叉树类，以及一个关联的 TreeNode 类，并希望生成一个由以下递归调用创建的二叉树:

f(n) = f(n-1) + f(n-2) for a given value of n

我想将其添加为我的二叉树类的 InsertFibonacci 方法，以替换标准的 Insert 方法:

def insertNode(self, root, inputData):
    if root == None:
        return self.addNode(inputData)
    else:
        if inputData <= root.nodeData:
            root.left = self.insertNode(root.left, inputData)
        else:
            root.right = self.insertNode(root.right, inputData)
        return root

我会向 Fib 函数添加某种装饰器吗？

# Fib function
def f(n):

    def helper(n):
        left = f(n-1)
        right = f(n-2)
        return left,right

    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        left, right = helper(n)
        return left + right

Answer 1

这是我能想到的最简单的解决方案:

class FibTree(object):
    def __init__(self, n):
        self.n = n
        if n < 2:
            self.value = n
        else:
            self.left = FibTree(n - 1)
            self.right = FibTree(n - 2)
            self.value = self.left.value + self.right.value