疑问：平衡BST检查代码中为何用max计算节点高度

Great question! Let's break down exactly what this line does and why it's essential for both calculating tree height and verifying balance.

First, let's recall the definition of a node's height in a binary tree:

A node's height is the length of the longest path from that node to any leaf node in its subtree. We count nodes in this path (so a leaf node has a height of 1, and an empty tree has a height of 0, which matches the base case in your code).

Why take the maximum of left and right subtree heights? #

The max(left_height, right_height) part ensures we're capturing the longest possible path from the current node to a leaf. Here's why that matters:

• If the left subtree is taller than the right, the longest path from the current node to a leaf goes through the left subtree. So we use left_height as the base.
• If the right subtree is taller, we use right_height instead.
• Adding 1 accounts for the current node itself in that longest path.

What happens if we didn't use max? #

Suppose we mistakenly used min(left_height, right_height) + 1 instead. Let's say we have a node where:

• Left subtree is a chain of 3 nodes (height = 3)
• Right subtree is a single leaf (height = 1)

Using min would give us a current node height of 1 + 1 = 2, which is wrong—this node's actual height should be 3 + 1 = 4 (since the longest path goes through the left chain). Worse, while the balance check abs(left_height - right_height) > 1 would still catch the 2-height difference here, miscalculating heights elsewhere in the tree could lead to completely incorrect balance judgments.

How this ties to the balanced check #

The core of the balanced BST logic relies on knowing the true heights of each subtree. By calculating the height correctly with max(...) + 1, we ensure that when we check abs(left_height - right_height) > 1, we're comparing the actual longest paths of the left and right subtrees. This is exactly what defines a balanced tree: no two sibling subtrees differ in height by more than 1.

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