算法与数据结构基础¶

# === 复杂度直观演示 ===
import time  # 导入时间模块

def demo_o1(data):
    """O(1)：常数时间——不管列表多长，只取第一个"""
    return data[0]  # 直接按索引取值，一步到位

def demo_on(data):
    """O(n)：线性时间——数据翻倍，时间翻倍"""
    total = 0  # 初始化累加器
    for x in data:  # 遍历每一个元素
        total += x  # 累加
    return total  # 返回总和

def demo_on2(data):
    """O(n²)：平方时间——两层循环，数据翻倍时间变4倍"""
    count = 0  # 初始化计数器
    for i in data:  # 外层循环
        for j in data:  # 内层循环（对每个i都遍历全部j）
            count += 1  # 每一对(i,j)都计数
    return count  # 返回总配对数

# 测试不同规模
for size in [1000, 5000, 10000]:  # 逐步增大数据量
    data = list(range(size))  # 生成测试数据

    start = time.time()  # 记录开始时间
    demo_on(data)  # 运行O(n)
    t_n = time.time() - start  # 计算耗时

    start = time.time()  # 记录开始时间
    demo_on2(data)  # 运行O(n²)
    t_n2 = time.time() - start  # 计算耗时

    print(f"n={size:>6}: O(n)={t_n:.6f}s, O(n²)={t_n2:.6f}s")
    # 你会看到 n 翻 5 倍时，O(n) 耗时翻 5 倍，O(n²) 耗时翻 25 倍

# === 列表基本操作 ===
genes = ["BRCA1", "TP53", "EGFR", "KRAS"]  # 创建基因列表

# 按索引访问——O(1)，直接跳到第2个位置
print(genes[1])  # 输出: TP53

# 末尾添加——O(1)
genes.append("MYC")  # 在最后面加一个基因
print(genes)  # ['BRCA1', 'TP53', 'EGFR', 'KRAS', 'MYC']

# 中间插入——O(n)，后面的元素都要往后挪
genes.insert(2, "PIK3CA")  # 在索引2的位置插入
print(genes)  # ['BRCA1', 'TP53', 'PIK3CA', 'EGFR', 'KRAS', 'MYC']

# 遍历——O(n)
for i, gene in enumerate(genes):  # enumerate 同时给出索引和值
    print(f"索引{i}: {gene}")  # 打印每个基因及其位置

# 列表推导式——Python特色的高效写法
lengths = [len(g) for g in genes]  # 计算每个基因名的长度
print(lengths)  # [5, 4, 6, 4, 4, 3]

# 切片操作——取子列表
top3 = genes[:3]  # 取前3个元素
print(top3)  # ['BRCA1', 'TP53', 'PIK3CA']

# === 字典基本操作 ===

# 基因 -> 功能的映射
gene_function = {  # 创建字典
    "BRCA1": "DNA修复",  # key: value 对
    "TP53": "肿瘤抑制",
    "EGFR": "细胞增殖信号",
}

# 查找——O(1)，直接通过key定位
print(gene_function["TP53"])  # 输出: 肿瘤抑制

# 添加——O(1)
gene_function["KRAS"] = "信号转导"  # 新增一个键值对

# 安全查找——key不存在时不报错
result = gene_function.get("BRAF", "未知功能")  # 找不到就返回默认值
print(result)  # 输出: 未知功能

# 遍历所有键值对
for gene, func in gene_function.items():  # .items() 返回键值对
    print(f"{gene}: {func}")

# === 生信实战：k-mer 计数 ===
def count_kmers(sequence, k):
    """统计序列中所有长度为k的子串出现次数"""
    kmer_counts = {}  # 空字典，用来存计数结果
    for i in range(len(sequence) - k + 1):  # 滑动窗口遍历
        kmer = sequence[i:i+k]  # 截取长度为k的子串
        # 如果这个kmer已经见过，计数+1；没见过就初始化为1
        kmer_counts[kmer] = kmer_counts.get(kmer, 0) + 1
    return kmer_counts  # 返回计数字典

seq = "ATCGATCGATCG"  # 测试序列
result = count_kmers(seq, 3)  # 统计3-mer
print(result)  # {'ATC': 3, 'TCG': 3, 'CGA': 2, 'GAT': 2}
# 哈希表让每次查找和更新都是O(1)，处理百万序列也很快

# === 集合基本操作 ===

# 两个样本中检测到的基因集合
sample_a = {"BRCA1", "TP53", "EGFR", "KRAS", "MYC"}  # 样本A的基因
sample_b = {"TP53", "EGFR", "PIK3CA", "BRAF", "MYC"}  # 样本B的基因

# 交集——两个样本共有的基因
common = sample_a & sample_b  # & 是交集运算符
print(f"共有基因: {common}")  # {'TP53', 'EGFR', 'MYC'}

# 并集——两个样本所有出现过的基因
all_genes = sample_a | sample_b  # | 是并集运算符
print(f"所有基因: {all_genes}")

# 差集——样本A有但B没有的基因
a_only = sample_a - sample_b  # - 是差集运算符
print(f"A独有: {a_only}")  # {'BRCA1', 'KRAS'}

# 成员判断——O(1)，非常快
print("BRCA1" in sample_a)  # True——在集合中查找是O(1)
print("BRCA1" in ["BRCA1", "TP53"])  # True——但在列表中查找是O(n)

# === 实战：从大列表中去重 ===
raw_reads = ["ATCG", "GCTA", "ATCG", "TTTT", "GCTA", "ATCG"]  # 原始reads，有重复
unique_reads = set(raw_reads)  # 一行去重
print(f"去重前: {len(raw_reads)}, 去重后: {len(unique_reads)}")
# 去重前: 6, 去重后: 3

# === 栈——用列表实现 ===
stack = []  # 空栈
stack.append("第1步: 读取FASTQ")  # 压入栈（push）
stack.append("第2步: 质控")  # 压入栈
stack.append("第3步: 比对")  # 压入栈

print(stack.pop())  # 弹出栈顶（pop）: "第3步: 比对"
print(stack.pop())  # 弹出: "第2步: 质控"
# 栈的应用：函数调用栈、撤销操作、括号匹配

# === 队列——用 collections.deque 实现 ===
from collections import deque  # deque 是双端队列，两头操作都是O(1)

task_queue = deque()  # 创建空队列
task_queue.append("样本001")  # 入队（队尾加入）
task_queue.append("样本002")  # 入队
task_queue.append("样本003")  # 入队

print(task_queue.popleft())  # 出队（队首弹出）: "样本001"
print(task_queue.popleft())  # 出队: "样本002"
# 队列的应用：任务调度、BFS搜索、流水线处理

# === 简单链表实现 ===
class Node:
    """链表节点：每个节点存一个值和指向下一个节点的指针"""
    def __init__(self, data):
        self.data = data  # 节点存储的数据
        self.next = None  # 指向下一个节点的指针，初始为空

class LinkedList:
    """单向链表"""
    def __init__(self):
        self.head = None  # 链表头部，初始为空

    def prepend(self, data):
        """在头部插入——O(1)"""
        new_node = Node(data)  # 创建新节点
        new_node.next = self.head  # 新节点指向原来的头
        self.head = new_node  # 更新头部为新节点

    def display(self):
        """遍历打印——O(n)"""
        current = self.head  # 从头开始
        items = []  # 收集所有值
        while current:  # 一直走到末尾（None）
            items.append(current.data)  # 记录当前值
            current = current.next  # 移动到下一个
        print(" -> ".join(items))  # 用箭头连接打印

# 使用链表
pipeline = LinkedList()  # 创建空链表
pipeline.prepend("比对")  # 插入到头部
pipeline.prepend("质控")  # 插入到头部（变成第一个）
pipeline.prepend("读取")  # 插入到头部（变成第一个）
pipeline.display()  # 输出: 读取 -> 质控 -> 比对

# === 二叉搜索树实现 ===
class TreeNode:
    """树节点"""
    def __init__(self, val):
        self.val = val  # 节点值
        self.left = None  # 左子节点
        self.right = None  # 右子节点

class BST:
    """二叉搜索树：左小右大"""
    def __init__(self):
        self.root = None  # 根节点

    def insert(self, val):
        """插入值——O(log n) 平均"""
        if not self.root:  # 空树，直接设为根
            self.root = TreeNode(val)
            return
        self._insert(self.root, val)  # 递归插入

    def _insert(self, node, val):
        """递归找到合适位置插入"""
        if val < node.val:  # 比当前节点小，往左走
            if node.left is None:  # 左边为空，就插在这里
                node.left = TreeNode(val)
            else:
                self._insert(node.left, val)  # 左边不空，继续往左找
        else:  # 比当前节点大或等于，往右走
            if node.right is None:  # 右边为空，就插在这里
                node.right = TreeNode(val)
            else:
                self._insert(node.right, val)  # 右边不空，继续往右找

    def search(self, val):
        """查找值——O(log n) 平均"""
        return self._search(self.root, val)

    def _search(self, node, val):
        """递归查找"""
        if node is None:  # 走到空了，没找到
            return False
        if val == node.val:  # 找到了
            return True
        elif val < node.val:  # 目标比当前小，往左找
            return self._search(node.left, val)
        else:  # 目标比当前大，往右找
            return self._search(node.right, val)

    def inorder(self, node, result=None):
        """中序遍历——会得到从小到大的排序结果"""
        if result is None:
            result = []  # 初始化结果列表
        if node:
            self.inorder(node.left, result)  # 先遍历左子树
            result.append(node.val)  # 再访问当前节点
            self.inorder(node.right, result)  # 最后遍历右子树
        return result

# 使用二叉搜索树
bst = BST()
expression_values = [5.2, 3.1, 7.8, 1.0, 4.5, 6.3, 9.9]  # 基因表达量
for val in expression_values:  # 逐个插入
    bst.insert(val)

print(bst.search(4.5))  # True——O(log n) 查找
print(bst.inorder(bst.root))  # [1.0, 3.1, 4.5, 5.2, 6.3, 7.8, 9.9]——排好序了

# === 用字典表示图（邻接表） ===

# 蛋白质互作网络（PPI Network）
ppi_network = {  # 每个蛋白质 -> 与它互作的蛋白质列表
    "TP53": ["MDM2", "BRCA1", "ATM"],  # TP53 和这3个蛋白质有互作
    "BRCA1": ["TP53", "RAD51", "BARD1"],
    "MDM2": ["TP53"],
    "ATM": ["TP53", "BRCA1"],
    "RAD51": ["BRCA1"],
    "BARD1": ["BRCA1"],
}

# 查找某个蛋白质的互作伙伴——O(1)
print(f"TP53的互作: {ppi_network['TP53']}")

# 计算每个蛋白质的度（degree = 连接数）
for protein, partners in ppi_network.items():
    print(f"{protein}: degree = {len(partners)}")
# TP53 degree=3，是这个网络中的 hub 蛋白（连接最多）

# 判断两个蛋白质是否有直接互作
def has_interaction(network, protein_a, protein_b):
    """判断两个蛋白质是否直接互作"""
    if protein_a in network:  # 先确保蛋白质a在网络中
        return protein_b in network[protein_a]  # 判断b是否在a的邻居中
    return False

print(has_interaction(ppi_network, "TP53", "MDM2"))  # True
print(has_interaction(ppi_network, "RAD51", "MDM2"))  # False

def quick_sort(arr):
    """快速排序——分而治之"""
    if len(arr) <= 1:  # 0或1个元素不用排，直接返回
        return arr
    pivot = arr[len(arr) // 2]  # 选中间的元素作为基准
    left = [x for x in arr if x < pivot]  # 比基准小的放左边
    middle = [x for x in arr if x == pivot]  # 等于基准的放中间
    right = [x for x in arr if x > pivot]  # 比基准大的放右边
    return quick_sort(left) + middle + quick_sort(right)  # 递归排序后拼接

# 测试：按表达量排序基因
expression = [5.2, 1.1, 8.7, 3.3, 6.6, 2.2]  # 基因表达量
sorted_exp = quick_sort(expression)  # 排序
print(sorted_exp)  # [1.1, 2.2, 3.3, 5.2, 6.6, 8.7]

def merge_sort(arr):
    """归并排序——先拆后合"""
    if len(arr) <= 1:  # 一个元素不用排
        return arr
    mid = len(arr) // 2  # 找中间位置
    left = merge_sort(arr[:mid])  # 递归排序左半部分
    right = merge_sort(arr[mid:])  # 递归排序右半部分
    return merge(left, right)  # 合并两个有序数组

def merge(left, right):
    """合并两个有序数组"""
    result = []  # 存放合并结果
    i = j = 0  # 两个指针分别指向left和right的开头
    while i < len(left) and j < len(right):  # 两边都还有元素
        if left[i] <= right[j]:  # 左边当前元素更小
            result.append(left[i])  # 放入结果
            i += 1  # 左指针前进
        else:  # 右边当前元素更小
            result.append(right[j])  # 放入结果
            j += 1  # 右指针前进
    result.extend(left[i:])  # 左边剩余的全部放入
    result.extend(right[j:])  # 右边剩余的全部放入
    return result

# 测试
data = [38, 27, 43, 3, 9, 82, 10]  # 待排序数据
print(merge_sort(data))  # [3, 9, 10, 27, 38, 43, 82]

def binary_search(arr, target):
    """二分查找——前提是数组已排序"""
    left, right = 0, len(arr) - 1  # 左右边界
    while left <= right:  # 还有搜索空间
        mid = (left + right) // 2  # 取中间位置
        if arr[mid] == target:  # 正好找到
            return mid  # 返回索引
        elif arr[mid] < target:  # 中间值太小，目标在右半边
            left = mid + 1  # 移动左边界
        else:  # 中间值太大，目标在左半边
            right = mid - 1  # 移动右边界
    return -1  # 没找到

# 测试：在排好序的染色体位置中查找
positions = [100, 250, 500, 750, 1000, 1500, 2000, 3000]  # 已排序的变异位点
idx = binary_search(positions, 750)  # 查找位置750
print(f"找到位置750在索引: {idx}")  # 输出: 3
print(f"查找999: {binary_search(positions, 999)}")  # 输出: -1（没找到）

def two_sum_sorted(arr, target):
    """在有序数组中找两个数的和等于target"""
    left, right = 0, len(arr) - 1  # 左右两个指针
    while left < right:  # 两个指针没相遇
        current_sum = arr[left] + arr[right]  # 当前两数之和
        if current_sum == target:  # 找到了
            return (left, right)  # 返回两个索引
        elif current_sum < target:  # 和太小，左指针右移让和变大
            left += 1
        else:  # 和太大，右指针左移让和变小
            right -= 1
    return None  # 没找到

# 测试：找两个表达量之和等于10
values = [1.5, 2.3, 3.7, 4.8, 6.2, 7.5, 8.1]  # 已排序
result = two_sum_sorted(values, 10.0)  # 找和为10的两个数
if result:
    i, j = result
    print(f"values[{i}]={values[i]} + values[{j}]={values[j]} = {values[i]+values[j]}")

def gc_content_windows(sequence, window_size):
    """用滑动窗口计算序列每个区域的GC含量"""
    results = []  # 存放每个窗口的GC含量
    # 先算第一个窗口的GC数
    gc_count = sum(1 for c in sequence[:window_size] if c in "GC")
    results.append(gc_count / window_size)  # 第一个窗口的GC含量

    # 窗口滑动：每次减去离开窗口的碱基，加上进入窗口的碱基
    for i in range(1, len(sequence) - window_size + 1):
        if sequence[i - 1] in "GC":  # 离开窗口的碱基是GC
            gc_count -= 1  # GC计数减1
        if sequence[i + window_size - 1] in "GC":  # 进入窗口的碱基是GC
            gc_count += 1  # GC计数加1
        results.append(gc_count / window_size)  # 记录当前窗口GC含量

    return results

# 测试
seq = "ATCGGCTAGCTTAAGCGCTA"  # 测试序列
gc_profile = gc_content_windows(seq, 5)  # 窗口大小5
for i, gc in enumerate(gc_profile):
    print(f"位置{i}-{i+4}: GC={gc:.1%}")  # 打印每个窗口的GC含量
# 滑动窗口让每个窗口的计算是O(1)，总时间O(n)
# 如果每个窗口都重新数一遍就是O(n*k)，窗口越大越慢

def fibonacci(n, memo={}):
    """斐波那契数列——带记忆化的递归
    注意：memo={} 利用了 Python 可变默认参数在函数调用间共享的特性来做缓存。
    面试中如果被问到可变默认参数的陷阱，要能解释这里是故意利用这个行为。
    更规范的写法是用 functools.lru_cache 装饰器。
    """
    if n <= 1:  # 基线条件：不再递归
        return n
    if n in memo:  # 已经算过了，直接返回（避免重复计算）
        return memo[n]
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2)  # 递归调用
    return memo[n]

# 测试
for i in range(10):
    print(f"F({i}) = {fibonacci(i)}", end="  ")
# F(0)=0  F(1)=1  F(2)=1  F(3)=2  F(4)=3  F(5)=5 ...
print()

# === 递归遍历进化树 ===
def count_leaves(tree):
    """递归计算树的叶子节点数（物种数）"""
    if isinstance(tree, str):  # 叶子节点是字符串（物种名）
        return 1  # 基线条件
    total = 0  # 初始化计数
    for subtree in tree:  # 遍历每个子树
        total += count_leaves(subtree)  # 递归计算
    return total

# 一个简单的进化树结构（嵌套列表表示）
phylo_tree = [["人类", "黑猩猩"], ["大猩猩", ["猩猩", "长臂猿"]]]
print(f"物种数: {count_leaves(phylo_tree)}")  # 输出: 5

# === 经典动态规划：爬楼梯 ===
def climb_stairs(n):
    """爬n级楼梯，每次爬1或2级，有多少种方法？"""
    if n <= 2:  # 1级有1种，2级有2种
        return n
    dp = [0] * (n + 1)  # dp[i] = 到第i级的方法数
    dp[1] = 1  # 到第1级只有1种方法
    dp[2] = 2  # 到第2级有2种方法（1+1 或 2）
    for i in range(3, n + 1):  # 从第3级开始推导
        dp[i] = dp[i-1] + dp[i-2]  # 从i-1跨1步 或 从i-2跨2步
    return dp[n]

print(f"爬10级楼梯: {climb_stairs(10)}种方法")  # 89

# === 生信核心：简化版序列比对（编辑距离） ===
def edit_distance(seq1, seq2):
    """计算两条序列的编辑距离（最少需要多少次操作变成一样）
    操作包括：插入、删除、替换
    这就是序列比对的简化版原理！
    """
    m, n = len(seq1), len(seq2)  # 两条序列的长度
    # dp[i][j] = seq1前i个字符 变成 seq2前j个字符 需要的最少操作数
    dp = [[0] * (n + 1) for _ in range(m + 1)]  # 创建 (m+1) x (n+1) 的表

    for i in range(m + 1):  # 第一列：seq2为空，需要删除i次
        dp[i][0] = i
    for j in range(n + 1):  # 第一行：seq1为空，需要插入j次
        dp[0][j] = j

    for i in range(1, m + 1):  # 逐行填表
        for j in range(1, n + 1):  # 逐列填表
            if seq1[i-1] == seq2[j-1]:  # 当前字符相同，不需要操作
                dp[i][j] = dp[i-1][j-1]  # 直接继承左上角的值
            else:  # 当前字符不同，取三种操作的最小值 + 1
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # 删除（从上方来）
                    dp[i][j-1],    # 插入（从左方来）
                    dp[i-1][j-1]   # 替换（从左上方来）
                )
    return dp[m][n]  # 右下角就是最终答案

# 测试
seq1 = "ATCGTAC"  # 序列1
seq2 = "ATGCTAC"  # 序列2
dist = edit_distance(seq1, seq2)
print(f"'{seq1}' 和 '{seq2}' 的编辑距离: {dist}")  # 2
# BLAST、Smith-Waterman、Needleman-Wunsch 都基于类似的DP思想

from collections import deque  # BFS需要队列

# 基因调控网络
gene_network = {
    "TP53": ["MDM2", "CDKN1A", "BAX"],  # TP53 调控这3个基因
    "MDM2": ["TP53"],  # 负反馈
    "CDKN1A": ["CDK2"],
    "BAX": ["BCL2"],
    "CDK2": [],
    "BCL2": [],
}

def bfs(graph, start):
    """BFS广度优先——一层一层往外扩展"""
    visited = set()  # 记录已访问的节点（避免重复）
    queue = deque([start])  # 初始化队列，放入起始节点
    visited.add(start)  # 标记起始节点为已访问
    order = []  # 记录访问顺序

    while queue:  # 队列不为空就继续
        node = queue.popleft()  # 取出队首节点
        order.append(node)  # 记录访问顺序
        for neighbor in graph.get(node, []):  # 遍历所有邻居
            if neighbor not in visited:  # 没访问过的才加入
                visited.add(neighbor)  # 标记为已访问
                queue.append(neighbor)  # 加入队尾
    return order

def dfs(graph, start, visited=None):
    """DFS深度优先——一条路走到底再回头"""
    if visited is None:
        visited = set()  # 初始化已访问集合
    visited.add(start)  # 标记当前节点为已访问
    order = [start]  # 记录当前节点
    for neighbor in graph.get(start, []):  # 遍历邻居
        if neighbor not in visited:  # 没访问过的
            order.extend(dfs(graph, neighbor, visited))  # 递归深入
    return order

print(f"BFS从TP53出发: {bfs(gene_network, 'TP53')}")
# ['TP53', 'MDM2', 'CDKN1A', 'BAX', 'CDK2', 'BCL2']——一层一层
print(f"DFS从TP53出发: {dfs(gene_network, 'TP53')}")
# ['TP53', 'MDM2', 'CDKN1A', 'CDK2', 'BAX', 'BCL2']——一条路走到底

def two_sum(nums, target):
    """给定数组和目标值，找出和为目标值的两个数的索引
    思路：用哈希表记录"需要的配对值"
    时间O(n)，空间O(n)
    """
    seen = {}  # 哈希表：值 -> 索引
    for i, num in enumerate(nums):  # 遍历每个数
        complement = target - num  # 计算需要的配对值
        if complement in seen:  # 配对值之前见过
            return [seen[complement], i]  # 返回两个索引
        seen[num] = i  # 记录当前值和索引
    return []  # 没找到

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]——因为 2+7=9

def is_valid_parentheses(s):
    """判断括号字符串是否有效
    思路：左括号压栈，右括号弹栈匹配
    """
    stack = []  # 用列表模拟栈
    pairs = {')': '(', ']': '[', '}': '{'}  # 右括号 -> 对应的左括号
    for char in s:  # 遍历每个字符
        if char in pairs:  # 是右括号
            if not stack or stack[-1] != pairs[char]:  # 栈空或不匹配
                return False  # 无效
            stack.pop()  # 匹配成功，弹出栈顶
        else:  # 是左括号
            stack.append(char)  # 压入栈
    return len(stack) == 0  # 最后栈空才是有效的

print(is_valid_parentheses("()[]{}"))  # True
print(is_valid_parentheses("(]"))  # False

class ListNode:
    """链表节点"""
    def __init__(self, val=0, next=None):
        self.val = val  # 值
        self.next = next  # 下一个节点

def reverse_list(head):
    """反转链表
    思路：三指针法，逐个翻转指向
    """
    prev = None  # 前一个节点，初始为空
    curr = head  # 当前节点，从头开始
    while curr:  # 还没到末尾
        next_temp = curr.next  # 先保存下一个节点（不然翻转后就丢了）
        curr.next = prev  # 当前节点指向前一个（翻转！）
        prev = curr  # 前指针前进
        curr = next_temp  # 当前指针前进
    return prev  # prev 现在是新的头节点

# 构建测试链表: 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = reverse_list(head)  # 反转
# 打印结果
node = new_head
while node:
    print(node.val, end=" -> " if node.next else "\n")  # 4 -> 3 -> 2 -> 1
    node = node.next

def max_subarray(nums):
    """找到数组中连续子数组的最大和
    思路：Kadane算法——维护当前最大和，如果加上当前数反而变小就重新开始
    生信联系：找基因组上信号最强的连续区段
    """
    max_sum = nums[0]  # 全局最大和，初始为第一个元素
    current_sum = nums[0]  # 当前连续和
    for i in range(1, len(nums)):  # 从第二个元素开始
        # 要么加上当前数继续延伸，要么从当前数重新开始
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)  # 更新全局最大
    return max_sum

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6（子数组[4,-1,2,1]）

class TreeNode:
    """二叉树节点"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root):
    """计算二叉树最大深度
    思路：递归——树的深度 = max(左子树深度, 右子树深度) + 1
    生信联系：计算进化树的最大进化距离
    """
    if root is None:  # 空节点深度为0（基线条件）
        return 0
    left_depth = max_depth(root.left)  # 递归算左子树深度
    right_depth = max_depth(root.right)  # 递归算右子树深度
    return max(left_depth, right_depth) + 1  # 取较大的+1（加上自己这一层）

# 构建测试树:     3
#               / \
#              9   20
#                 / \
#                15   7
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(f"最大深度: {max_depth(root)}")  # 3

def min_distance(word1, word2):
    """计算将word1转换为word2所需的最少操作次数
    操作：插入、删除、替换
    这道题就是序列比对的核心算法！
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]  # DP表

    # 初始化：空串到另一个串需要的操作数
    for i in range(m + 1):
        dp[i][0] = i  # word1前i个字符全删除
    for j in range(n + 1):
        dp[0][j] = j  # 空串插入j个字符

    # 填表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:  # 字符相同
                dp[i][j] = dp[i-1][j-1]  # 不需要操作
            else:  # 字符不同，三种操作取最小
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # 删除word1[i]
                    dp[i][j-1],    # 在word1中插入word2[j]
                    dp[i-1][j-1]   # 替换word1[i]为word2[j]
                )
    return dp[m][n]

# 生信示例：两条DNA序列的编辑距离
print(min_distance("ATCGTAC", "ATGCTAC"))  # 2
print(min_distance("GATTACA", "GCATGCU"))  # 4