直径、高度与平衡树
使用一次 DFS 遍历和同时返回两个值的辅助函数计算树的直径与高度，然后检查树是否高度平衡。
直径、高度与平衡树 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
二叉树的高度
二叉树的高度（或最大深度）是从根节点到任意叶节点的最长路径长度。它可以通过递归计算：任意节点的高度为 1 + max(height(left), height(right))，空节点的基本情况为 0。这种后序计算非常基础——高度是计算直径、检查平衡性以及执行 AVL 树旋转的基础。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(root):
if not root:
return 0
return 1 + max(height(root.left), height(root.right))
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root)) # 4直径：最长路径
二叉树的直径是任意两个节点之间的最长路径长度（这条路径不一定经过根节点）。路径长度以边为单位。对于任意节点，经过该节点的直径等于 height(left) + height(right)。整棵树的直径就是树中所有节点对应值的最大值。
def diameter_of_binary_tree(root):
max_diameter = [0] # use list to allow closure mutation
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Diameter through this node
max_diameter[0] = max(max_diameter[0], left_h + right_h)
return 1 + max(left_h, right_h) # height for parent
dfs(root)
return max_diameter[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root)) # 3只需一次 DFS 遍历计算直径
朴素方法会在每个节点调用 height()，对于平衡树来说时间复杂度为 O(n²)。最优解法在一次 DFS 遍历中同时计算高度并更新直径。关键在于，递归函数 dfs() 同时承担两个作用：向父节点返回高度，同时通过副作用更新全局最大直径。这种双重用途的后序模式会出现在许多树问题中。
# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
if not root:
return 0
through_root = height(root.left) + height(root.right)
in_left = diameter_naive(root.left)
in_right = diameter_naive(root.right)
return max(through_root, in_left, in_right)
# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')平衡二叉树检查
如果每个节点的左右子树高度之差最多为一，则该二叉树是高度平衡的。蛮力方法会在每个节点调用 height()，时间复杂度为 O(n²)。最优方法使用相同的一次遍历技巧：使用 -1 作为“不平衡”的哨兵值并向上传递，一旦发现某个节点不平衡就提前停止。
def is_balanced(root):
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1 # propagate early exit
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1 # unbalanced here
return 1 + max(left, right) # height if balanced
return check(root) != -1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5) # too deep on left
print(is_balanced(root)) # False哨兵返回值模式
返回一个哨兵值（不平衡时返回 -1，或返回一个特殊元组）是一种常见模式，适用于 DFS 辅助函数需要传递两类信息的情况：计算结果，以及是否违反了约束。不要抛出异常或使用全局标志，而是将错误编码在返回类型中。这种方法简洁、避免了全局状态，并且能自然地与其他递归辅助函数组合。
# General pattern: return (is_valid, computed_value)
def balanced_height(node):
if not node:
return True, 0
left_ok, left_h = balanced_height(node.left)
if not left_ok:
return False, 0 # short-circuit
right_ok, right_h = balanced_height(node.right)
if not right_ok:
return False, 0
balanced = abs(left_h - right_h) <= 1
return balanced, 1 + max(left_h, right_h)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h) # True 2以节点数还是边数表示直径
请注意题目描述：LeetCode #543 以边为单位计算直径，而有些问题以节点为单位计算。如果需要计算节点数，经过某个节点的直径为 height(left) + height(right) + 1（为节点自身加 1）。如果需要计算边数，则省略 +1。开始编码前，请务必先与面试官确认这一点。
def diameter_in_nodes(root):
max_path = [0]
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Path through this node in NODE count
nodes_through = left_h + right_h + 1
max_path[0] = max(max_path[0], nodes_through)
return 1 + max(left_h, right_h)
dfs(root)
return max_path[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root)) # 4 nodes: 4-2-1-3 or 5-2-1-3路径和：任意根节点到叶节点的路径
路径和问题要求判断：是否存在一条从根节点到叶节点的路径，其路径和等于目标值？使用 DFS，并在向下遍历时从目标值中减去当前节点的值。在叶节点处，检查剩余目标值是否等于该叶节点的值。这是一种传递剩余和作为参数的前序 DFS，是自顶向下递归的经典例子。
def has_path_sum(root, target):
if not root:
return False
# Leaf node: check if we've exactly hit the target
if not root.left and not root.right:
return root.val == target
remaining = target - root.val
return (has_path_sum(root.left, remaining) or
has_path_sum(root.right, remaining))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5+4+11+2=22最大路径和（困难变体）
最大路径和（LeetCode #124）要难得多：路径可以从任意节点开始并在任意节点结束，而不只是从根节点到叶节点，并且节点值可能为负数。在每个节点处，需要考虑四种情况：只有该节点、节点加左分支、节点加右分支，或节点加左右两个分支。只有前三种情况可以继续向上延伸到父节点；第四种情况是全局最大值的终止候选值。
def max_path_sum(root):
max_sum = [float('-inf')]
def gain(node):
if not node:
return 0
# Only take positive contributions
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
# Best path through this node (can't go both ways upward)
max_sum[0] = max(max_sum[0], node.val + left + right)
# Return the best single-branch gain for parent
return node.val + max(left, right)
gain(root)
return max_sum[0]
root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root)) # 42: 15+20+7AVL 树与自平衡
AVL 树是一种通过在插入和删除操作后执行旋转来保持高度平衡性质的 BST。每个节点都存储一个平衡因子（右子树高度减去左子树高度），其值必须保持在 {-1, 0, 1} 之内。发生违反平衡条件的情况时，单旋转或双旋转可以在 O(1) 时间内恢复平衡，使整体高度保持为 O(log n)，并保证所有操作的复杂度为 O(log n)。
# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node
# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root
# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')对称树检查
如果一棵二叉树是自身的镜像，则它是对称的。可以递归检查：对于对称轴两侧的每一对对应节点，如果它们的值相等且子树互为镜像，则该树是对称的。定义辅助函数 is_mirror(left, right)，检查以下情况：两者都为空（可以），一个为空（不可以），值相等且内侧与外侧子树互为镜像。
def is_symmetric(root):
def is_mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return is_mirror(root.left, root.right)
sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym)) # True
nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym)) # False结合高度与直径的要点
单次遍历的后序模式可以复用于许多问题：直径、最大路径和、检查平衡性、统计优质节点等。在解决问题时，请始终思考：“父节点需要从每个子节点获得什么信息？”这就是返回值。“当前节点的局部计算是什么？”它会更新全局答案。这种拆解是解决复杂树问题的关键技能。
# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
result = [float('-inf')] # or 0 depending on problem
def dfs(node):
if not node:
return 0 # base return (height, count, etc.)
left_val = dfs(node.left)
right_val = dfs(node.right)
# --- Update global result using both children ---
candidate = left_val + right_val # example: diameter
result[0] = max(result[0], candidate)
# --- Return info needed by PARENT ---
return 1 + max(left_val, right_val) # example: height
dfs(root)
return result[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root)) # diameter = 2快速检查
请测试您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：使用递归后序 DFS 计算高度，使用具有双重用途的 DFS 辅助函数在单次 O(n) 遍历中计算直径，以及使用提前退出标记进行平衡性检查。接下来我们将学习路径总和问题和最低公共祖先。
常见问题解答
「直径、高度与平衡树」课时是免费的吗？
是的 — 「直径、高度与平衡树」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「直径、高度与平衡树」这节课中我会学到什么？
使用一次 DFS 遍历和同时返回两个值的辅助函数计算树的直径与高度，然后检查树是否高度平衡。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「直径、高度与平衡树」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。