二叉搜索树平衡检查代码解析：高度计算与递归栈原理

首先先把你提供的代码格式化清晰：

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. height = max(left_height, right_height) + 1 如何计算树的高度 #

这行代码完全贴合树的高度定义来实现：

• 代码里把空节点的高度定为0（就是base case里的返回值）
• 非空节点的高度 = 它左右子树中更高的那个子树的高度 + 1（加1是因为当前节点本身要算一层）

举几个具体例子帮你理解：

• 如果当前节点是叶子节点（左右子节点都是空），那么left_height和right_height都是0，max(0,0)+1 = 1，也就是叶子节点的高度为1，这符合我们对树高度的认知。
• 如果当前节点有一个左子节点（叶子，高度1）和一个空的右子节点（高度0），那么max(1,0)+1 = 2，当前节点的高度就是2，代表从当前节点到最远叶子节点有2层（当前节点+左叶子）。
• 这行代码的核心逻辑是：每个节点的高度由它最深的那条分支决定，毕竟树的高度本来就是根节点到最远叶子节点的路径上的节点总数。

2. 递归栈的调用逻辑（is_left_balanced... 和 is_right_balanced...） #

递归调用遵循**深度优先遍历（DFS）**的规则，我用一个简单的树结构模拟栈的变化，你就能明白整个过程：

A
   / \
  B   C
 /
D

栈的完整追踪过程： #

1. 初始调用 is_balanced(A)，把这个调用压入栈，暂停后续代码执行。
2. 在is_balanced(A)里，先执行 is_balanced(B)，把is_balanced(B)压入栈，暂停is_balanced(A)的执行。
3. 在is_balanced(B)里，执行 is_balanced(D)，把is_balanced(D)压入栈，暂停is_balanced(B)的执行。
4. 在is_balanced(D)里，先调用 is_balanced(D.left)（空节点），这个调用直接触发base case返回(True, 0)，不需要压栈。
5. 回到is_balanced(D)，接下来调用 is_balanced(D.right)（空节点），同样返回(True, 0)。
6. 现在is_balanced(D)可以计算高度、检查平衡，返回(True, 1)给is_balanced(B)，is_balanced(D)从栈中弹出。
7. 回到is_balanced(B)，接下来调用 is_balanced(B.right)（空节点），返回(True, 0)。
8. is_balanced(B)计算高度max(1,0)+1=2，检查平衡（左右高度差1，符合要求），返回(True, 2)给is_balanced(A)，is_balanced(B)从栈中弹出。
9. 回到is_balanced(A)，现在才开始执行 is_balanced(C)，把is_balanced(C)压入栈。
10. 在is_balanced(C)里，先调用is_balanced(C.left)（空）返回(True,0)，再调用is_balanced(C.right)（空）返回(True,0)。
11. is_balanced(C)计算高度1，返回(True,1)给is_balanced(A)，is_balanced(C)从栈中弹出。
12. 最后is_balanced(A)计算高度max(2,1)+1=3，检查平衡（左右高度差1，符合要求），返回(True,3)，栈彻底清空。

关键结论： #

• 递归栈总是先把当前节点左子树的所有递归调用处理完（一直深入到最左的空节点，再逐层回溯），完全搞定左子树后，才会开始处理当前节点的右子树调用。
• 每一层递归调用都会在栈里保留当前的执行状态（比如已经执行到哪一行、变量的临时值），只有等子调用返回结果后，才会继续执行当前函数剩下的代码。

内容的提问来源于stack exchange，提问作者anon anon