我想在递归循环展开时添加值

Question

这是一种自下而上的方法来检查树是否是 AVL 树。那么这段代码的工作原理是：

假设这是一棵树:

检查叶子节点是否为叶子节点（此处为1）。当数据为 2 的节点是当前值时，它会展开一个递归。 cl = 1 的值，同时它比较正确的树。 2 的右分支是空的，即没有任何 children，所以 avl_compare 将有 (1, 0)，这是允许的。

这之后我想给cl加一个值，这样当数据为3的节点为当前值时，cl的值=2。avl_check是一道赋值题。我自己完成了这个，但我需要一些帮助来玩递归函数。

def avl_check(self):

    cl = cr = 0
    if(self.left):
        self.left.avl_check()
        cl+=1

    if(self.right):
        self.right.avl_check()
        cr += 1

    if(not self.avl_compare(cl,cr)):
            print("here")

Answer 1

您的直接问题是您似乎不了解局部变量和全局变量。 cl 和 cr 是局部变量；对于给定的控制流，它们唯一可以拥有的值是 0 和 1。请记住，例程的每个实例都会获得一组新的局部变量：您将它们设置为 0，也许递增到 1，然后您 return.这确实不会影响函数其他实例中的变量值。

一个更深层次的问题是你没有考虑到更大的树。假设您学会使用全局变量并纠正这些增量。拿你当前的树，插入节点 4、9、10 和 11（非常平衡）。遍历您的算法，跟踪 cl 和 cr 的值。当您到达节点 10 时，cl 令人不安地超过了树的深度——我认为这是您逻辑中的致命错误。

再想一想：递归例程不应该有全局变量，除了动态编程实现的数据存储（这里不适用）。该函数应检查基本情况和 return 一些微不足道的东西（例如 0 或 1）。否则，函数应该将问题减少一个简单的步骤并重现；当递归 returns 时，函数对结果做一些简单的事情，然后 returns 将新结果传给它的父级。

你的任务比较简单：

Find the depths of the two subtrees.
If their difference > 1, return False
else return True

你应该已经知道如何检查树的深度了。先实现这个。之后，使您的实现更加智能：检查子树的深度应该也在每一步检查其平衡。这将是您的最终解决方案。

我想在递归循环展开时添加值

I want to add values while a recursive loop unfolds

python

recursion

binary-tree

avl-tree