二叉树深度解析：从基础结构到平衡艺术

1# 节点数关系验证函数
2def verify_leaf_relation(nodes):
3    n0 = sum(1 for node in nodes if node.degree == 0)
4    n2 = sum(1 for node in nodes if node.degree == 2)
5    return n0 == n2 + 1

1根节点索引为0的方案：
2Parent(i) = (i-1)//2
3Left(i) = 2i+1
4Right(i) = 2i+2
5
6根节点索引为1的方案（常见于旧教材）：
7Parent(i) = i//2
8Left(i) = 2i
9Right(i) = 2i+1

1class BSTNode:
2    def __init__(self, val):
3        self.val = val
4        self.left = None
5        self.right = None
6
7def insert(root, val):
8    if not root:
9        return BSTNode(val)
10    if val < root.val:
11        root.left = insert(root.left, val)
12    else:
13        root.right = insert(root.right, val)
14    return root

1def rotate_right(y):
2    x = y.left
3    T2 = x.right
4    
5    x.right = y
6    y.left = T2
7    
8    y.height = 1 + max(get_height(y.left), get_height(y.right))
9    x.height = 1 + max(get_height(x.left), get_height(x.right))
10    
11    return x

1是否需要持久化存储？ 
2→ 是 → 考虑B+树
3→ 否 → 需要严格平衡？ 
4       → 是 → AVL树 
5       → 否 → 红黑树

1def serialize(root):
2    if not root:
3        return "None"
4    return f"{root.val},{serialize(root.left)},{serialize(root.right)}"
5
6def deserialize(data):
7    def helper(values):
8        val = next(values)
9        if val == "None":
10            return None
11        node = TreeNode(int(val))
12        node.left = helper(values)
13        node.right = helper(values)
14        return node
15    values = iter(data.split(","))
16    return helper(values)