Python二叉树

www.xservx.com · 蜀ICP备2026035467号-3

⚡二叉树基础认知

二叉树是数据结构中最基础且核心的非线性结构之一,由有限个节点构成的集合,该集合满足以下条件:

  • 每个节点最多有两棵子树,分别称为左子树与右子树
  • 左子树与右子树有严格的顺序性,不能任意颠倒
  • 二叉树可以为空集,此时称为空树

与树不同,二叉树的每个节点最多仅有两个子节点,且子节点位置固定。这种结构特性使其在算法设计、编译器实现、数据库索引等领域具有广泛应用。

在Python中,二叉树节点通常用类表示:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

这种定义方式简洁明了,符合Python面向对象设计哲学。其中:

  • val存储节点值,可为任意可哈希对象
  • left与right分别指向左右子节点,为空时设为None

值得注意的是,Python标准库并未内置二叉树结构,需开发者自行实现。这也使得二叉树成为学习算法与数据结构的理想载体——既不过于复杂,又能充分展现递归、迭代、内存管理等核心编程思想。

从计算机科学教育角度看,二叉树是连接基础编程与高级算法的桥梁。例如,在学习递归时,二叉树的遍历(前序、中序、后序)是经典案例;在理解动态规划时,树形DP问题常以二叉树为载体;在掌握图算法时,二叉搜索树(BST)又是图论与树结构的交汇点。

更进一步地,二叉树的变体(如平衡二叉树、红黑树、AVL树)构成了现代数据库索引与操作系统内存管理的理论基础。例如,MySQL的InnoDB引擎使用B+树(二叉树的推广)实现聚簇索引;Linux内核的CFS调度器使用红黑树管理进程控制块;而Python的dict与set底层虽采用哈希表,但在某些版本中也引入了树结构优化内存布局。

因此,深入掌握二叉树不仅有助于通过技术面试,更是构建扎实计算机科学知识体系的关键一步。

〔二叉树的数学定义〕

形式化地,二叉树可递归定义为:

二叉树是n(n≥0)个节点的有限集合,该集合或为空树(n=0),或由一个根节点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

该定义强调了二叉树的递归特性——任何子树本身仍是二叉树。这一特性为递归算法设计提供了理论基础,例如:

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

上述代码计算二叉树高度,其时间复杂度为O(n),空间复杂度(递归栈)为O(h),其中h为树高。

〔二叉树的存储结构〕

二叉树主要有两种存储方式:

  1. 链式存储:如上述TreeNode类,通过指针连接节点。优点是灵活高效,适用于动态插入删除;缺点是访问子节点需遍历指针,缓存局部性较差。
  2. 顺序存储:用数组存储节点,下标关系满足:
    • 父节点下标i的左子节点为2i+1,右子节点为2i+2
    • 子节点下标i的父节点为floor((i-1)/2)

顺序存储适用于完全二叉树(如堆结构),可避免指针开销;但对稀疏树结构会造成大量空间浪费。例如,高度为h的单支树(所有节点只有左子节点)在顺序存储中需2h-1个数组位置,而实际仅用h个节点。

〔二叉树的基本性质〕

二叉树具有以下重要性质:

  1. 第i层最多有2i-1个节点(i≥1)
  2. 高度为h的二叉树最多有2h-1个节点
  3. 对任意二叉树,叶子节点数n0与度为2的节点数n2满足:n0 = n2 + 1
  4. 完全二叉树的节点数n与高度h满足:h = floor(log2n) + 1

这些性质为算法复杂度分析提供理论依据。例如,平衡二叉树的高度为O(log n),使得查找、插入、删除等操作的时间复杂度可控制在O(log n)内。

〔二叉树 vs 二叉搜索树〕

需特别注意:二叉树是通用数据结构,而二叉搜索树(Binary Search Tree, BST)是满足特定性质的二叉树:

  • 左子树所有节点值 < 根节点值
  • 右子树所有节点值 > 根节点值
  • 左右子树也均为二叉搜索树

该性质使BST支持O(log n)时间复杂度的查找操作(在平衡前提下),成为动态集合的高效实现方式。

⚙️二叉树构建方法

构建二叉树是学习数据结构的入门实践。根据输入形式不同,常见构建方式包括:

〔1. 层次遍历构建〕

输入为层次遍历序列(如[1,2,3,None,4]),常用于LeetCode题目:

from collections import deque
def build_tree_from_level_order(nodes):
    if not nodes or nodes[0] is None:
        return None
    root = TreeNode(nodes[0])
    queue = deque([root])
    i = 1
    while queue and i < len(nodes):
        node = queue.popleft()
        if i < len(nodes) and nodes[i] is not None:
            node.left = TreeNode(nodes[i])
            queue.append(node.left)
        i += 1
        if i < len(nodes) and nodes[i] is not None:
            node.right = TreeNode(nodes[i])
            queue.append(node.right)
        i += 1
    return root

该算法时间复杂度为O(n),空间复杂度为O(w),其中w为树的最大宽度。适用于完全二叉树及完全不二叉树的构建。

〔2. 前序+中序构建〕

已知前序遍历与中序遍历可唯一确定一棵二叉树:

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

关键点在于中序序列中根节点位置将序列分为左右子树,前序序列中根节点后紧跟左子树节点。时间复杂度O(n2)(因index操作),可优化为O(n)(用哈希表预存中序索引)。

〔3. 后序+中序构建〕

类似地,后序序列末尾为根节点:

def build_tree_post_in(postorder, inorder):
    if not postorder or not inorder:
        return None
    root_val = postorder[-1]
    root = TreeNode(root_val)
    mid = inorder.index(root_val)
    root.left = build_tree_post_in(postorder[:mid], inorder[:mid])
    root.right = build_tree_post_in(postorder[mid:-1], inorder[mid+1:])
    return root

构建过程体现了递归思想的核心——将大问题分解为规模更小的同类子问题。

〔4. 手动构建典型示例〕

以下构建一棵典型二叉搜索树:

root = TreeNode(8)
root.left = TreeNode(3)
root.right = TreeNode(10)
root.left.left = TreeNode(1)
root.left.right = TreeNode(6)
root.left.right.left = TreeNode(4)
root.left.right.right = TreeNode(7)
root.right.right = TreeNode(14)
root.right.right.left = TreeNode(13)

该树结构如下:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

此结构是后续所有算法实现的基础,建议读者亲手绘制并验证遍历结果。

〔5. 复杂场景:带父指针的二叉树〕

某些算法(如后序遍历的迭代实现)需父节点引用:

class TreeNodeWithParent:
    def __init__(self, val=0, left=None, right=None, parent=None):
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent

构建时需同步设置父指针,例如:

root = TreeNodeWithParent(1)
root.left = TreeNodeWithParent(2, parent=root)
root.right = TreeNodeWithParent(3, parent=root)
root.left.left = TreeNodeWithParent(4, parent=root.left)

此类设计在树路径回溯、 Lowest Common Ancestor(LCA)等算法中非常实用。

🔍二叉树遍历算法

遍历是二叉树操作的基础,分为递归与非递归两种实现方式。根据访问顺序不同,可分为:

〔1. 递归遍历〕

递归遍历最符合人类思维,代码简洁清晰:

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

递归遍历的时间复杂度为O(n),空间复杂度为O(h)(递归栈深度)。对平衡树为O(log n),对单支树为O(n)。

〔2. 迭代遍历〕

迭代遍历避免递归调用开销,需显式使用栈:

def preorder_iterative(root):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

关键点:先压入右子节点,再压入左子节点,确保左子节点先出栈。

def inorder_iterative(root):
    stack, result = [], []
    current = root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

中序遍历需模拟“最左节点”路径,利用栈暂存路径节点。

def postorder_iterative(root):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]

后序遍历可反向思维:根→右→左的逆序即左→右→根。此技巧显著简化实现。

〔3. Morris遍历〕

Morris遍历是空间复杂度O(1)的遍历方法,通过临时修改树结构实现:

def morris_inorder(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            pre = current.left
            while pre.right and pre.right != current:
                pre = pre.right
            if not pre.right:
                pre.right = current
                current = current.left
            else:
                pre.right = None
                result.append(current.val)
                current = current.right
    return result

Morris遍历的核心是“线索化”——临时将前驱节点的右指针指向当前节点。虽然修改了树结构,但遍历完成后恢复原状,不影响后续操作。该方法适用于内存受限场景,如嵌入式设备。

〔4. 层序遍历(BFS)〕

层序遍历使用队列实现,按层级访问节点:

from collections import deque
def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

该算法可进一步扩展为“之字形层序遍历”(Zigzag Level Order),通过奇偶层反转实现:

def zigzag_level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    left_to_right = True
    while queue:
        level_size = len(queue)
        level = deque()
        for _ in range(level_size):
            node = queue.popleft()
            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(list(level))
        left_to_right = not left_to_right
    return result

此变体常用于可视化树结构,增强层次感。

〔5. 遍历应用实例〕

遍历是许多树算法的基础,例如:

  • 求最大深度:后序遍历中取左右子树深度最大值+1
  • 验证二叉搜索树:中序遍历结果应严格递增
  • 路径求和:前序遍历中累加路径值,叶节点判断是否满足条件
  • 对称二叉树:中序遍历结果应为回文串(需结合其他条件)

这些应用体现了遍历作为“操作骨架”的核心地位。

🌳二叉搜索树(BST)详解

二叉搜索树(Binary Search Tree, BST)是满足以下性质的二叉树:

  • 左子树所有节点值 < 根节点值
  • 右子树所有节点值 > 根节点值
  • 左右子树也均为二叉搜索树

该性质使BST支持高效查找、插入、删除操作(平均O(log n)时间复杂度),是动态集合的首选数据结构。

〔1. BST基础操作〕

查找操作:

def search_bst(root, target):
    if not root or root.val == target:
        return root
    if target < root.val:
        return search_bst(root.left, target)
    return search_bst(root.right, target)

时间复杂度O(h),h为树高。对平衡BST为O(log n),对单支树为O(n)。

插入操作:

def insert_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    return root

插入位置唯一,即保持BST性质的叶节点位置。

删除操作:

def delete_bst(root, key):
    if not root:
        return root
    if key < root.val:
        root.left = delete_bst(root.left, key)
    elif key > root.val:
        root.right = delete_bst(root.right, key)
    else:
        # 三种情况:无子节点、单子节点、双子节点
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # 双子节点:找右子树最小值替代
        min_larger = root.right
        while min_larger.left:
            min_larger = min_larger.left
        root.val = min_larger.val
        root.right = delete_bst(root.right, min_larger.val)
    return root

删除双子节点时,需找到右子树最小值(或左子树最大值)替代根节点,确保BST性质不变。

〔2. BST验证〕

验证一棵树是否为BST,中序遍历法最直观:

def is_bst(root):
    def inorder(node, prev):
        if not node:
            return True, prev
        left_valid, prev = inorder(node.left, prev)
        if not left_valid or (prev is not None and node.val <= prev):
            return False, node.val
        return inorder(node.right, node.val)
    return inorder(root, None)[0]

更优方法是递归验证每个节点值是否在有效范围内:

def is_bst_range(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if not (min_val < root.val < max_val):
        return False
    return (is_bst_range(root.left, min_val, root.val) and
            is_bst_range(root.right, root.val, max_val))

该方法避免了中序遍历的额外空间开销,时间复杂度O(n),空间复杂度O(h)。

〔3. BST变体:AVL树〕

标准BST在极端情况下(如顺序插入)会退化为单支树,时间复杂度退化为O(n)。AVL树通过旋转操作维持平衡,确保树高为O(log n)。

AVL树定义:任意节点左右子树高度差不超过1。

插入操作需维护平衡因子(左高-右高),并通过以下旋转调整:

  • LL旋转:左子树的左子树过高 → 右旋
  • RR旋转:右子树的右子树过高 → 左旋
  • LR旋转:左子树的右子树过高 → 左旋+右旋
  • RL旋转:右子树的左子树过高 → 右旋+左旋

以下为LL旋转实现:

def rotate_right(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

AVL树的旋转操作是理解平衡树的核心,其思想被广泛应用于红黑树、伸展树等自平衡结构中。

〔4. BST应用实例〕

有序流数据处理:

class StreamChecker:
    def __init__(self):
        self.root = None
    def add(self, val):
        self.root = insert_bst(self.root, val)
    def get_sorted(self):
        return inorder(self.root)

该设计支持动态添加数据并获取有序序列,适用于实时排序场景。

区间查询:

def range_query(root, low, high):
    if not root:
        return []
    result = []
    if low < root.val:
        result.extend(range_query(root.left, low, high))
    if low <= root.val <= high:
        result.append(root.val)
    if high > root.val:
        result.extend(range_query(root.right, low, high))
    return result

该算法时间复杂度为O(k + log n),其中k为结果数量,显著优于暴力遍历。

⚖️AVL树深度解析

AVL树(Adelson-Velsky and Landis Tree)是最早被发明的自平衡二叉搜索树,其核心思想是通过旋转操作维持树的平衡性,确保任何节点的左右子树高度差不超过1。

〔1. 平衡因子定义〕

节点的平衡因子 = 左子树高度 - 右子树高度

AVL树要求所有节点的平衡因子 ∈ {-1, 0, 1}

〔2. 插入操作的四种旋转〕

LL情况(左子树过高,且插入在左子树的左侧):

右旋操作将左子节点提升为根节点:

def rotate_right(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

旋转后平衡因子恢复为0。

RR情况(右子树过高,且插入在右子树的右侧):

左旋操作将右子节点提升为根节点:

def rotate_left(y):
    x = y.right
    T2 = x.left
    # 旋转
    x.left = y
    y.right = 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

LR情况(左子树过高,但插入在左子树的右侧):

先左旋左子树,再右旋整棵树:

def rotate_lr(root):
    root.left = rotate_left(root.left)
    return rotate_right(root)

RL情况(右子树过高,但插入在右子树的左侧):

先右旋右子树,再左旋整棵树:

def rotate_rl(root):
    root.right = rotate_right(root.right)
    return rotate_left(root)

〔3. 删除操作的平衡调整〕

删除操作可能导致节点失衡,需从删除位置向上检查并旋转:

def delete_avl(root, key):
    # ... 删除逻辑(与BST相同)...
    # 更新高度
    root.height = 1 + max(get_height(root.left), get_height(root.right))
    # 检查平衡因子
    balance = get_balance(root)
    # 四种失衡情况
    if balance > 1:
        if get_balance(root.left) >= 0:  # LL
            return rotate_right(root)
        else:  # LR
            root.left = rotate_left(root.left)
            return rotate_right(root)
    if balance < -1:
        if get_balance(root.right) <= 0:  # RR
            return rotate_left(root)
        else:  # RL
            root.right = rotate_right(root.right)
            return rotate_left(root)
    return root

删除操作可能引发连续失衡,需逐层向上调整,时间复杂度O(log n)。

〔4. AVL树性能分析〕

时间复杂度:

操作平均情况最坏情况
查找O(log n)O(log n)
插入O(log n)O(log n)
删除O(log n)O(log n)

由于严格平衡,AVL树性能稳定,但旋转操作开销较大。

空间复杂度:

  • 每个节点需存储高度信息(额外O(1)空间)
  • 递归实现需O(log n)栈空间

〔5. AVL树 vs 红黑树〕

虽然AVL树查找性能更优,但红黑树在插入/删除时旋转次数更少,因此:

  • AVL树适用于查找密集型场景(如数据库索引)
  • 红黑树适用于插入/删除频繁场景(如C++ STL的map/set)

Python的dict与set采用哈希表而非平衡树,但其设计思想(如碰撞处理、扩容机制)与树结构有异曲同工之妙。

🔗线索二叉树

线索二叉树通过利用空指针域存储前驱/后继信息,实现非递归遍历且无需栈空间。

〔1. 线索化原理〕

在二叉树中,n个节点共有2n个指针域:

  • n-1个用于指向子节点
  • n+1个为空指针

线索化将空指针域改为指向前驱或后继节点。

〔2. 线索化节点定义〕

class ThreadedNode:
    def __init__(self, val=0, left=None, right=None,
                 lthread=True, rthread=True):
        self.val = val
        self.left = left
        self.right = right
        self.lthread = lthread  # True表示left是线索
        self.rthread = rthread  # True表示right是线索

线索化需在遍历过程中建立线索:

def inorder_threading(root):
    def inorder(node, prev):
        if not node:
            return prev
        prev = inorder(node.left, prev)
        if not node.left:
            node.left = prev
            node.lthread = True
        if prev and not prev.right:
            prev.right = node
            prev.rthread = True
        return inorder(node.right, node)
    # 添加头节点简化操作
    head = ThreadedNode()
    head.left = root
    head.lthread = False
    if root:
        prev = inorder(root, head)
        prev.right = head
        prev.rthread = True
    return head

〔3. 线索二叉树遍历〕

中序线索二叉树的遍历无需栈:

def inorder_traversal_threaded(head):
    result = []
    current = head.right  # 第一个节点
    while current and current != head:
        result.append(current.val)
        if current.rthread:
            current = current.right
        else:
            current = current.right
            while not current.lthread:
                current = current.left

时间复杂度O(n),空间复杂度O(1)。

〔4. 线索二叉树的应用场景〕

  • 内存受限环境:如嵌入式设备中无法使用栈
  • 频繁遍历场景:避免重复计算前驱/后继
  • 并行算法:线索化后可并行遍历子树

现代数据库系统(如SQLite)在B+树节点中也采用类似思路存储前驱指针,加速范围查询。

⛰️堆结构与二叉树

堆(Heap)是基于完全二叉树实现的优先队列,满足:

  • 最大堆:父节点值 ≥ 子节点值
  • 最小堆:父节点值 ≤ 子节点值

〔1. 堆的数组实现〕

完全二叉树可用数组紧凑存储:

class MinHeap:
    def __init__(self):
        self.heap = []
    def parent(self, i):
        return (i - 1) // 2
    def left_child(self, i):
        return 2 * i + 1
    def right_child(self, i):
        return 2 * i + 2

〔2. 堆操作实现〕

上滤(插入):

def heap_insert(heap, val):
    heap.append(val)
    i = len(heap) - 1
    while i > 0 and heap[parent(i)] > heap[i]:
        heap[i], heap[parent(i)] = heap[parent(i)], heap[i]
        i = parent(i)

下滤(删除):

def heapify(heap, i):
    smallest = i
    left = left_child(i)
    right = right_child(i)
    if left < len(heap) and heap[left] < heap[smallest]:
        smallest = left
    if right < len(heap) and heap[right] < heap[smallest]:
        smallest = right
    if smallest != i:
        heap[i], heap[smallest] = heap[smallest], heap[i]
        heapify(heap, smallest)

〔3. 堆的应用〕

  • Top K问题:维护大小为k的最小堆
  • 合并K个有序链表:用堆选择最小节点
  • 堆排序:建堆O(n),排序O(n log n)

〔4. Python内置堆〕

Python的heapq模块实现最小堆:

import heapq
# 建堆
heap = [3, 1, 4, 1, 5]
heapq.heapify(heap)
# 插入
heapq.heappush(heap, 9)
# 删除最小值
min_val = heapq.heappop(heap)

注意:heapq仅支持最小堆,最大堆可通过取反实现。

💻二叉树应用场景

〔1. 表达式树〕

表达式树是二叉树的典型应用,叶节点为操作数,内部节点为操作符:

    +
   / \
  *   5
 / \
3   2

对应表达式:(3 * 2) + 5 = 11

计算表达式值可用后序遍历:

def eval_expr_tree(root):
    if not root.left and not root.right:
        return root.val
    left_val = eval_expr_tree(root.left)
    right_val = eval_expr_tree(root.right)
    if root.val == '+':
        return left_val + right_val
    elif root.val == '-':
        return left_val - right_val
    elif root.val == '*':
        return left_val * right_val
    else:
        return left_val / right_val

〔2. 字典树(Trie)〕

字典树是多叉树,常用于字符串查找:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

虽然非二叉树,但其递归结构与二叉树思想一致。

〔3. 决策树〕

机器学习中决策树用于分类,每个节点为特征判断:

  • 根节点:最有效特征
  • 内部节点:次级特征
  • 叶节点:分类结果

决策树的构建涉及信息增益、基尼指数等计算,与二叉树遍历密切相关。

〔4. 文件系统树〕

操作系统文件系统采用树形结构组织目录:

/
├── home/
│   ├── user/
│   │   ├── documents/
│   │   └── downloads/
│   └── admin/
└── var/
    └── log/

遍历目录树是二叉树应用的扩展,支持递归查找、文件统计等操作。

〔5. 网页DOM树〕

HTML文档的DOM结构是树形结构:

<html>
  <head>...</head>
  <body>
    <div>
      <p>Hello</p>
    </div>
  </body>
</html>

JavaScript操作DOM树时,常使用递归遍历节点。

📚LeetCode高频题解

〔1. 二叉树最大深度(104)〕

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

递归求解,时间复杂度O(n),空间复杂度O(h)。

〔2. 对称二叉树(101)〕

def is_symmetric(root):
    def is_mirror(t1, t2):
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        return (t1.val == t2.val and
                is_mirror(t1.left, t2.right) and
                is_mirror(t1.right, t2.left))
    return is_mirror(root, root)

关键:比较左右子树是否镜像对称。

〔3. 路径总和(112)〕

def has_path_sum(root, target_sum):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target_sum
    return (has_path_sum(root.left, target_sum - root.val) or
            has_path_sum(root.right, target_sum - root.val))

前序遍历中累加路径值,叶节点判断是否满足条件。

〔4. 二叉树的最大路径和(124)〕

路径可任意起点终点,但不能分叉:

def max_path_sum(root):
    max_sum = float('-inf')
    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max(dfs(node.left), 0)
        right_gain = max(dfs(node.right), 0)
        # 当前节点作为最高点的路径和
        current_path = node.val + left_gain + right_gain
        max_sum = max(max_sum, current_path)
        # 返回单侧最大路径
        return node.val + max(left_gain, right_gain)
    dfs(root)
    return max_sum

该题考察全局最优解与局部最优解的权衡。

〔5. 二叉搜索树中第K小的元素(230)〕

def kth_smallest(root, k):
    stack = []
    current = root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        k -= 1
        if k == 0:
            return current.val
        current = current.right

利用BST中序遍历有序的性质。