我正在查看这个python代码来检查二叉搜索树是否平衡。但是,我想知道是否有人可以解释如何
height = max(left_height, right_height) + 1
发挥作用。这行代码如何计算高度。最后,这是如何
is_left_balanced, left_height = TreeNode.is_balanced(cur_node.left)
is_right_balanced, right_height = TreeNode.is_balanced(cur_node.right)
堆栈递归正在工作,因为一旦调用了 is_balanced(cur_node.left(,当调用第二个 TreeNode.is_balanced(cur_node.right( 时会再次调用它。
我无法遵循堆栈跟踪。
以下是整个代码:
def is_balanced(cur_node) :
if (not cur_node) :
height = 0
return True, height
is_left_balanced, left_height = TreeNode.is_balanced(cur_node.left)
is_right_balanced, right_height = TreeNode.is_balanced(cur_node.right)
#To get the height of the current node, we find the maximum of the
#left subtree height and the right subtree height and add 1 to it
height = max(left_height, right_height) + 1
if (not is_left_balanced or not is_right_balanced):
return False, height
#If the difference between height of left subtree and height of
#right subtree is more than 1, then the tree is unbalanced
if (abs(left_height - right_height) > 1):
return False, height
return True, height
在处理递归问题时,您应该始终注意基本情况是什么。在这个程序中,只有一个基本情况:一棵空树,它的高度为 1,并且根据定义是平衡的。 现在假设一棵树是不平衡的,如果它最高的一半的高度大于 1 加上它的另一半的高度(也就是说,它最高的一半至少高出两个级别(,或者如果它的子树之一不平衡,那么我们得到一种递归方法来计算它。
首先,为平凡平衡(空(树返回 0 和 True。我们得到了基本情况。
其次,如果其中两半不平衡,则树不平衡。这是针对每个子树检查的,因此递归将继续进行,直到找到一棵空树,在那里它将开始返回(想象一下只有一个级别,一个节点的树的情况。想象一下代码将如何运行,您可能可以从那里进行推断(。
最后,如果每个子树都是平衡的(这是第三种情况,因为我们已经进入了程序(,那么树不平衡的唯一方式是它的一颗子树比另一棵子树高出一个以上。我们只是检查它,并返回与该值相反的值。
我希望这能帮助您理解,否则请随时问我任何其他问题!