Python 二叉树

什么是二叉树?

二叉树(Binary Tree)是计算机科学中一种基础且关键的非线性数据结构,由有限个节点组成的集合。每个节点最多有两棵子树,分别称为左子树与右子树,且子树有严格的左右次序,不可颠倒。这种“最多两个子节点”的特性,使其在递归建模、搜索优化、排序压缩等领域展现出不可替代的价值。

与数组、链表等线性结构不同,二叉树天然具备层级关系,其高度(从根节点到最深叶子节点的最长路径长度)直接决定操作的时间复杂度上限。理想情况下,平衡二叉树的高度为 O(log₂n),而退化为链表时则退化为 O(n)。这一特性决定了二叉树在工程实践中必须结合自平衡机制使用。

在Python生态中,二叉树虽无内置实现,但其灵活的类定义、元组嵌套、字典建模等方式为开发者提供了高度自由的建模空间。更重要的是,Python的递归机制与生成器语法,使其成为演示树形算法的理想语言——既保留了教学的清晰性,又支持工业级性能优化。

二叉树的核心特征

  • ⑴ 每个节点至多拥有两个子节点(度≤2)
  • ⑵ 左右子树有序——交换左右子树构成不同二叉树
  • ⑶ 可为空树(节点数为0)
  • ⑷ 具有递归定义:子树本身也是二叉树
  • ⑸ 常见变体:满二叉树、完全二叉树、二叉搜索树、AVL树、红黑树、堆

值得注意的是,**满二叉树**(Full Binary Tree)要求每个非叶子节点都有两个子节点;而**完全二叉树**(Complete Binary Tree)则允许最后一层不满,但必须从左到右连续填充——这一特性使其可高效用数组存储(如堆实现)。**完美二叉树**(Perfect Binary Tree)则是前两者的交集,所有叶子节点在同一层,节点总数为 2ʰ - 1(h为高度)。

在算法竞赛与系统设计中,二叉树常作为更复杂结构的基石。例如,B+树索引本质是多叉搜索树,但其内部节点可视为二叉搜索树的泛化;哈夫曼编码树用于无损压缩,其构造依赖贪心策略与二叉树合并;表达式树直接映射算术表达式的语法结构,是编译原理中语法分析的直观模型。

二叉树的Python建模方式

Python中实现二叉树有多种路径,不同方式适用于不同场景:教学演示、算法竞赛、工程部署。核心考量点在于内存开销、访问效率与可读性平衡。

类定义法:面向对象建模

最标准、最易扩展的方式是定义节点类,通过对象引用构建树结构。该方式语义清晰,便于添加方法(如插入、删除、遍历),适合复杂业务场景。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
# 构建示例树:[1,2,3,null,4]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)

优势:⑴ 支持动态方法扩展(如`get_height()`);⑵ 调试友好(可直接打印节点值);⑶ 兼容Python对象序列化(pickle)。劣势:内存开销略高(每个节点含属性字典与引用开销)。

元组嵌套:轻量级表示

利用Python元组不可变特性,采用`(val, left, right)`三元组表示节点,空子树用`None`。适合函数式风格、Immutable数据流场景。

# 表示树:[1, (2, None, (4,)), (3,)]
tree = (1,
        (2, None, (4, None, None)),
        (3, None, None))
# 访问根值
root_val = tree[0]
# 访问左子树
left_subtree = tree[1]

优势:内存占用极低(元组无属性开销),天然不可变,线程安全。劣势:遍历逻辑需手写递归,缺乏封装性,调试困难(需手动索引)。常用于LeetCode题解的紧凑表示。

字典建模:动态配置友好

以字典存储节点,键名明确表达结构关系(如`value`、`left`、`right`),适合配置驱动场景(如从JSON加载树结构)。

tree = {
    'value': 1,
    'left': {
        'value': 2,
        'right': {'value': 4}
    },
    'right': {'value': 3}
}
# 遍历函数
def traverse(node):
    if not node: return []
    return [node['value']] + traverse(node['left']) + traverse(node['right'])

优势:JSON互操作性极佳,结构可读性强(键名自解释)。劣势:字典开销较大,递归深度受限于Python默认栈限制(约1000层),大规模树需改用迭代。

数组模拟:堆结构专用

对完全二叉树,可用数组按层序存储节点,索引i的左子为`2i+1`,右子为`2i+2`(0基)。这是堆(Heap)的底层实现方式,牺牲通用性换取极致性能。

# 数组表示完全二叉树 [1,2,3,4,5,6]
arr = [1, 2, 3, 4, 5, 6]
# 访问节点
i = 0  # 根节点
left = 2*i + 1   # → 1 (值2)
right = 2*i + 2  # → 2 (值3)
# 插入新节点(维护堆性质)
arr.append(7)  # 添加到末尾(最后一层最右)
# 上滤调整...

优势:无指针开销,缓存友好(连续内存),访问O(1)。劣势:仅适用于完全二叉树,非完全树需填充占位符,空间浪费严重。Python的`heapq`模块即基于此原理实现最小堆。

在工程实践中,**类定义法**是主流选择。Python的`dataclass`进一步简化了节点定义:

from dataclasses import dataclass
@dataclass
class TreeNode:
    val: int
    left: 'TreeNode' = None
    right: 'TreeNode' = None

该方式自动生成`__init__`、`__repr__`等方法,兼顾简洁性与可读性,是算法开发与教学的推荐方案。

二叉树遍历:递归、迭代与Morris

遍历是二叉树操作的基石,指按特定顺序访问所有节点。常见策略分为四类:前序(根→左→右)、中序(左→根→右)、后序(左→右→根)、层序(按层从左到右)。不同遍历对应不同应用场景:前序用于复制树,中序用于二叉搜索树输出有序序列,后序用于释放资源,层序用于广度优先搜索。

递归遍历:最简实现

递归利用函数调用栈隐式管理访问顺序,代码简洁,但深度过大可能引发栈溢出(Python默认递归深度约1000)。

# 前序遍历
def preorder(root):
    return [root.val] + preorder(root.left) + preorder(root.right) if root else []
# 中序遍历
def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []
# 后序遍历
def postorder(root):
    return postorder(root.left) + postorder(root.right) + [root.val] if root else []

递归的数学本质是分治思想:将树拆解为根、左子树、右子树三部分,递归求解子问题。中序遍历在二叉搜索树中尤为关键——输出结果严格递增,可验证树的合法性。

迭代遍历:显式栈模拟

为避免递归限制,需用显式栈模拟调用过程。以中序遍历为例:沿左子树一路入栈,到达空节点后弹栈访问,转向右子树。

def inorder_iterative(root):
    stack, res = [], []
    curr = root
    while stack or curr:
        while curr:          # 一路向左
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()   # 回溯
        res.append(curr.val) # 访问
        curr = curr.right    # 转右
    return res

迭代版时间复杂度O(n),空间复杂度O(h)(h为树高),最坏O(n)(退化为链表)。其优势在于可中断执行(如搜索到目标值提前退出),适合实时系统。

Morris遍历:O(1)空间的神技

Morris遍历通过临时修改树结构(建立线索指针)实现常数空间遍历,核心思想是利用叶子节点的空右指针指向中序后继节点。

def morris_inorder(root):
    res = []
    curr = root
    while curr:
        if not curr.left:      # 无左子树,直接访问
            res.append(curr.val)
            curr = curr.right
        else:
            # 找左子树最右节点(中序前驱)
            pre = curr.left
            while pre.right and pre.right != curr:
                pre = pre.right
            if not pre.right:  # 建线索
                pre.right = curr
                curr = curr.left
            else:              # 恢复树结构
                pre.right = None
                res.append(curr.val)
                curr = curr.right
    return res

Morris遍历将空间复杂度压至O(1),但需修改树结构(临时),遍历后恢复原状。适用于内存受限场景(如嵌入式设备),但不适用于并发环境(结构临时变动)。在LeetCode中,该算法是“二叉树中序遍历”题的最优解法(击败100%)。

层序遍历需借助队列实现广度优先搜索:

from collections import deque
def level_order(root):
    if not root: return []
    queue = deque([root])
    res = []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        res.append(level)
    return res  # [[1], [2,3], [4], ...]

该算法输出二维列表,每层一个子列表,是二叉树层次分析、最短路径(如最小深度)的基础。

二叉搜索树(BST):高效搜索的基石

二叉搜索树(Binary Search Tree)是一种特殊的二叉树,满足**左子树所有节点值 < 根节点值 < 右子树所有节点值**的性质。这一性质使BST支持高效查找、插入、删除操作,平均时间复杂度O(log n),是数据库索引、字典实现的核心数据结构。

BST的Python实现

class BSTNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
class BinarySearchTree:
    def __init__(self):
        self.root = None
    def insert(self, val):
        if not self.root:
            self.root = BSTNode(val)
            return
        curr = self.root
        while True:
            if val < curr.val:
                if not curr.left:
                    curr.left = BSTNode(val)
                    return
                curr = curr.left
            else:
                if not curr.right:
                    curr.right = BSTNode(val)
                    return
                curr = curr.right

插入操作沿树向下寻找空位,严格遵循大小关系。中序遍历BST必得升序序列,这是验证BST合法性的黄金标准:

def is_valid_bst(root):
    def inorder(node):
        if not node: return []
        return inorder(node.left) + [node.val] + inorder(node.right)
    vals = inorder(root)
    return vals == sorted(set(vals))  # 无重复值时

实际工程中,需额外处理重复值:常见策略是记录计数器(如红黑树的计数节点),或规定重复值统一放右子树(牺牲严格有序性换取简单性)。

查找与删除操作

查找:从根开始,值小向左,值大向右,值等返回。

def search(self, val):
    curr = self.root
    while curr:
        if val == curr.val: return True
        curr = curr.left if val < curr.val else curr.right
    return False

删除:分三种情况——⑴ 叶子节点:直接删除;⑵ 单子节点:子节点替代;⑶ 双子节点:找右子树最小值(或左子树最大值)替代,再删除该替代节点。

def delete(self, val):
    # ... 查找节点及父节点 ...
    if not node.left and not node.right:  # 叶子
        self._replace(parent, node, None)
    elif not node.left or not node.right:  # 单子
        child = node.left or node.right
        self._replace(parent, node, child)
    else:  # 双子
        # 找右子树最小值节点
        min_parent, min_node = node, node.right
        while min_node.left:
            min_parent, min_node = min_node, min_node.left
        node.val = min_node.val
        self._replace(min_parent, min_node, min_node.right)

BST的致命缺陷是可能退化为链表(如按升序插入),此时操作退化为O(n)。这引出了下文的自平衡树——通过旋转操作维持树高平衡。

AVL树:最早的自平衡二叉搜索树

AVL树(Adelson-Velsky and Landis Tree)是历史上第一种自平衡二叉搜索树,要求任意节点的左右子树高度差(平衡因子)绝对值≤1。通过旋转操作(单旋/双旋)动态维持平衡,确保操作复杂度严格O(log n)。

AVL的核心机制

  • ⑴ 插入/删除后,沿路径向上更新高度与平衡因子
  • ⑵ 当|平衡因子|>1时触发旋转
  • ⑶ 四种失衡模式:LL型(左左)、RR型(右右)、LR型(左右)、RL型(右左)
  • ⑷ 旋转操作:左旋、右旋、左右旋、右左旋

旋转本质是局部结构调整,不改变BST的中序遍历结果(保持有序性)。例如LL型失衡(左子树过高)通过右旋恢复平衡:

def right_rotate(y):
    x = y.left
    T2 = x.right
    # 旋转
    x.right = y
    y.left = T2
    # 更新高度
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    return x  # 新根

Python中实现AVL树需维护节点高度属性,插入/删除后递归回溯检查平衡性。其优势在于严格O(log n)性能,适合对最坏情况有硬性要求的场景(如金融交易系统)。劣势是旋转逻辑复杂,代码量大,常数因子高,实际性能可能不如红黑树。

AVL vs 红黑树

特性AVL树红黑树
平衡条件高度差≤1红黑规则(根黑、红无子红、等黑高)
最坏时间复杂度O(log n)O(log n)
查找性能略优(更矮)略差
插入/删除性能较慢(旋转多)较快(最多2次旋转)
应用查找密集型(数据库索引)插入/删除频繁(C++ map/set, Java TreeMap)

Python标准库的`dict`与`set`未使用AVL树,因其基于哈希表实现;而`sortedcontainers`第三方库提供排序列表与字典,底层为分块列表,非树结构。若需严格AVL树,可选用`bintrees`库(已停止维护)或自行实现。

堆(Heap):优先队列的高效实现

堆是满足特定性质的完全二叉树:**最大堆**(父≥子)用于实现最大优先队列,**最小堆**(父≤子)用于最小优先队列。堆支持O(1)取极值、O(log n)插入/删除,是Top-K问题、任务调度、Dijkstra算法的核心。

Python堆操作:heapq模块

Python内置`heapq`模块实现最小堆,通过列表存储树结构:

import heapq
# 创建堆
data = [3, 1, 4, 1, 5]
heapq.heapify(data)  # 原地建堆 → [1, 1, 4, 3, 5]
# 插入元素
heapq.heappush(data, 2)  # → [1, 1, 2, 3, 5, 4]
# 取最小值
min_val = heapq.heappop(data)  # → 1,剩余堆调整

最大堆可通过取负值模拟:

max_heap = []
for x in [3, 1, 4, 1, 5]:
    heapq.heappush(max_heap, -x)  # 存储负值
max_val = -heapq.heappop(max_heap)  # → 5

堆排序(Heap Sort)利用堆的性质实现原地排序,时间复杂度O(n log n),空间O(1),但不稳定(相等元素相对顺序可能改变):

def heap_sort(arr):
    heapq.heapify(arr)  # 建最小堆
    return [heapq.heappop(arr) for _ in range(len(arr))]  # 依次弹出

堆的典型应用场景

  • ⑴ **Top-K问题**:维护大小为K的最小堆,遍历数据流,新元素大于堆顶则替换堆顶并调整
  • ⑵ **合并K个有序链表**:用堆存储各链表当前最小节点
  • ⑶ **任务调度**:按优先级(堆值)分配CPU时间片
  • ⑷ **滑动窗口中位数**:双堆法(大顶堆存较小半,小顶堆存较大半)

在LeetCode中,堆题常以“第K大/小元素”“合并有序列表”“数据流中位数”等形式出现。例如“数据流的中位数”题(#295)需维护两个堆:`small`(最大堆)存较小一半,`large`(最小堆)存较大一半,确保`len(small) == len(large)`或`len(small) == len(large)+1`。

实战:LeetCode高频题精解

以下精选三道经典二叉树题,展示Python实现技巧与思维建模过程。

题1:二叉树的最大深度(#104)

给定二叉树根节点,求其最大深度(根到叶子节点的最长路径长度)。

def maxDepth(root):
    if not root: return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

递归解法简洁优雅,但存在递归深度限制。迭代版用BFS层序遍历计数:

def maxDepth_iter(root):
    if not root: return 0
    depth = 0
    queue = [root]
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.pop(0)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
    return depth

注意:`queue.pop(0)`是O(n)操作,应改用`collections.deque.popleft()`优化至O(1)。

题2:验证二叉搜索树(#98)

判断给定二叉树是否为合法BST。陷阱在于:仅检查父-子关系(左<根<右)不够,需保证**左子树所有节点<根<右子树所有节点**。

def isValidBST(root):
    def inorder(node, lower=float('-inf'), upper=float('inf')):
        if not node: return True
        val = node.val
        if val <= lower or val >= upper:
            return False
        # 递归检查右子树:下界更新为val
        if not inorder(node.right, val, upper):
            return False
        # 递归检查左子树:上界更新为val
        if not inorder(node.left, lower, val):
            return False
        return True
    return inorder(root)

该解法通过上下界约束,确保每个节点值在合法区间内,是BST验证的标准范式。

题3:二叉树的最近公共祖先(#236)

给定二叉树中两节点p、q,求其最近公共祖先(LCA)。经典解法:递归搜索左右子树,若当前节点为p或q则返回,否则合并左右子树结果。

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right: return root  # p、q分居两侧
    return left or right  # 同侧则返回非空结果

该算法假设p、q均存在于树中。若存在不存在情况,需先遍历检查节点存在性。

二叉树题目的核心思想是**分解为子问题**:父问题依赖子树结果,通过递归自底向上求解。掌握此范式,可应对90%以上树相关题目。

二叉树面试高频考点

根据牛客网、LeetCode中国社区数据,二叉树是算法面试Top 3考点(占比18%),高频题型包括:遍历变体、路径和、序列化/反序列化、树的直径、子树匹配等。

必考题型清单

  • ⑴ 前/中/后序遍历的迭代与Morris实现
  • ⑵ BST的插入、删除、查找操作
  • ⑶ 验证BST、恢复BST(一个节点被错误交换)
  • ⑷ 最近公共祖先(LCA)、最小距离
  • ⑸ 路径和问题(目标和路径、路径总数)
  • ⑹ 树的直径、最大路径和(#124)
  • ⑺ 序列化/反序列化二叉树
  • ⑻ 子树匹配(判断T是否为S的子树)

面试官常考察“陷阱题”,例如:给定先序和中序遍历序列,重建二叉树。关键点在于:先序序列首元素为根,中序序列中根左侧为左子树、右侧为右子树,递归构建。

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    root_idx = inorder.index(root_val)
    root.left = buildTree(preorder[1:1+root_idx], inorder[:root_idx])
    root.right = buildTree(preorder[1+root_idx:], inorder[root_idx+1:])
    return root

优化:用哈希表预存中序序列索引,避免每次O(n)查找,整体复杂度从O(n²)降至O(n)。

手写代码注意事项

  • ⑴ 边界条件:空树、单节点树
  • ⑵ 递归终止条件:`if not root`
  • ⑶ 变量命名清晰:`curr`, `prev`, `root`, `left`, `right`
  • ⑷ 时间/空间复杂度分析:面试官必问!
  • ⑸ 测试用例:补充空输入、极端情况

高级问题可能涉及:树同构、树哈希、树同态、树同胚。这些属于理论计算机科学范畴,工业场景较少涉及,但面试中可能作为加分彩蛋。