数据结构与算法基础

发表于 2026-06-29 更新于 2026-07-10 分类于教程， AI训练师

系统讲解数据结构与算法核心知识，涵盖数组、链表、栈、队列、树、图、哈希表及排序查找算法，补充链表逆置、快慢指针、括号匹配、表达式求值、循环队列、AVL树、红黑树、B树、邻接表、快速排序、归并排序、堆排序完整代码、BFS最短路径、DFS连通性判断与环检测等重点知识的具体操作步骤和代码实现，适合人工智能训练师系统学习及算法基础复习。

这是”人工智能训练师基础”系列第一篇讲义。作为概念基础，数据结构和算法是核心内容，概念密集、细节多，容易在这里混淆细节。所以把它单独拎出来，讲解那些常见算法算法——比如链表逆置怎么转指针、快慢指针到底怎么走、二分查找的边界为什么那样写、堆排序怎么从数组建堆。同时还补充了括号匹配、表达式求值、循环队列、二叉树迭代遍历、AVL树旋转、红黑树性质详解、B树磁盘适配原理、邻接表实现、快速排序/归并排序/堆排序、BFS求无权图最短路径、DFS连通性判断与环检测等关键知识点。每一段都配上输入输出示例和代码实现，让你能跟着走一遍，”听明白、能做题”。

第一章数据结构与算法：把数据摆明白，把套路用清楚

数据结构和算法是重点内容，概念点特别密集，关键就是常复习。

线性表：数组与链表的取舍

线性表是最基础的结构，元素排成一条线，元素之间是一对一的前后关系。这一节的真正重点不在”什么是线性表”，而在它的两种物理实现——数组和链表——各自的取舍。

数组，是连续内存里的一排座位，下标就是座位号。最大的好处是随机访问快，下标一给就能直接算出地址，时间复杂度 O(1)。代价是插入和删除很麻烦，中间插一个，后面所有人都要往后挪一个位置，O(n)。而且数组要事先定好大小，开多了浪费、开少了溢出。

链表正好反过来，内存不连续，靠指针把节点串起来，像一场寻宝游戏，每个节点只告诉你”下一个在哪”。它的好处是插入删除快，只要改几个指针就行，O(1) 就能搞定（前提是你已经站在了要操作的位置）。代价是访问慢，想拿第 100 个节点，得从头一个一个顺着指针走过去，O(n)。

这一组对比非常重要，记住一句话就够：”数组擅长查、链表擅长增删”。再延伸几个易混点：单链表只能往后走，双向链表前后都能走，循环链表尾节点指回头部。链表常见的算法有逆置、找中点（快慢指针）、判断是否有环（快慢指针追及），这几个套路一定要熟。下面就把这三个套路的具体操作步骤拆开讲。

链表逆置：三指针法

逆置链表最经典的写法是用三个指针：prev、curr、next。核心思路是”一边遍历一边把每个节点的 next 指针掉头指向前一个”。prev 记前一个节点，curr 记当前节点，next 临时存下一个节点

来个代码例子：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    curr = head
    while curr is not None:
        next_node = curr.next  # 先存下一个，别丢了
        curr.next = prev      # 掉头，指向前一个
        prev = curr           # prev 前进一步
        curr = next_node      # curr 前进一步
    return prev              # 循环结束时 prev 就是新头

快慢指针找中点

找链表中点用快慢指针，思路是”快的跑得快，慢的跑得慢，快的跑到尾时慢的正好在中点”。慢指针每次走一步，快指针每次走两步，快指针走到尾（None 或 next 是 None）时停下，慢指针所在位置就是中点。

来个代码例子：

def findMiddle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

快慢指针判断是否有环

判断链表有没有环也是快慢指针，但这里要的是”追及”——如果有环，快指针迟早会从后面追上慢指针；如果无环，快指针会先走到尾。

来个示例代码：

def hasCycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True   # 相遇了，有环
    return False          # 快指针走到头，无环

为什么一定能追上？因为快指针每轮比慢指针多走一步，在有环里每轮两者的距离缩小 1，迟早归零。这是弗洛伊德龟兔赛跑算法，名字有印象就行。

栈与队列：一个后进先出，一个先进先出

栈和队列本质上是”操作受限的线性表”，只能在特定位置进出，正是因为受限，才有了独特的性质。

栈是后进先出，缩写 LIFO，最形象的生活类比就是食堂里叠盘子，最后放上去的那个最先被拿走。它只允许在栈顶一端操作，进栈叫 push，出栈叫 pop。栈的典型应用场景你最好能背下来几个：函数调用（递归就是靠栈实现的）、括号匹配、表达式求值、浏览器的前进后退。看到”回退””撤销””配对””嵌套”这类词，第一反应就应该是栈。

括号匹配：用栈解决配对问题

括号匹配是栈的经典应用，核心思路是”遇到左括号就入栈，遇到右括号就和栈顶配对”。规则很简单：左括号必须和类型相同的右括号配对，而且必须正确嵌套。

具体步骤：

初始化一个空栈
遍历字符串中的每个字符：
- 如果是左括号（( [ {），push 进栈
- 如果是右括号，检查栈是否为空：
  - 空栈说明没有对应的左括号，返回 False
  - 非空则 pop 栈顶元素，判断是否匹配（) 对应 (，] 对应 [，} 对应 {）
  - 不匹配则返回 False
遍历结束后，检查栈是否为空：
- 空栈说明所有左括号都配对成功，返回 True
- 非空说明还有未配对的左括号，返回 False

代码：

def isValid(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)
    return not stack

表达式求值：双栈处理中缀表达式

表达式求值也是栈的核心应用，这里讲的是中缀表达式（就是我们平时写的 1+2*3）。思路是用两个栈：一个存操作数，一个存运算符。

规则：

遇到数字，直接入操作数栈
遇到运算符，比较它和栈顶运算符的优先级：
- 如果当前运算符优先级更高，直接入运算符栈
- 如果当前运算符优先级更低或相等，先弹出栈顶运算符，再弹出两个操作数计算，结果入操作数栈，重复直到当前运算符能入栈
遍历结束后，弹出运算符栈中剩余的所有运算符，依次计算
操作数栈中最后剩下的就是结果

代码：

def calculate(s):
    def priority(op):
        if op in '+-':
            return 1
        if op in '*/':
            return 2
        return 0
    
    num_stack = []
    op_stack = []
    num = 0
    
    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)
        elif char in '+-*/':
            num_stack.append(num)
            num = 0
            while op_stack and priority(op_stack[-1]) >= priority(char):
                b = num_stack.pop()
                a = num_stack.pop()
                op = op_stack.pop()
                if op == '+':
                    num_stack.append(a + b)
                elif op == '-':
                    num_stack.append(a - b)
                elif op == '*':
                    num_stack.append(a * b)
                elif op == '/':
                    num_stack.append(a // b)
            op_stack.append(char)
    num_stack.append(num)
    
    while op_stack:
        b = num_stack.pop()
        a = num_stack.pop()
        op = op_stack.pop()
        if op == '+':
            num_stack.append(a + b)
        elif op == '-':
            num_stack.append(a - b)
        elif op == '*':
            num_stack.append(a * b)
        elif op == '/':
            num_stack.append(a // b)
    
    return num_stack[0]

队列是先进先出，缩写 FIFO，类比排队买饭，先来的先服务。一端进（队尾 enqueue）、一端出（队头 dequeue）。队列最典型的应用是广度优先搜索（BFS）和各种排队调度场景。

这里有个容易混淆的点是循环队列。普通队列用数组实现时，队头出队后会留下空位却用不上，这叫”假溢出”。循环队列把数组首尾相连解决这问题，但判空判满要小心：通常约定牺牲一个单元，当 front==rear 时判空，当 (rear+1)%size==front 时判满，队列长度公式是 (rear-front+size)%size。这一串公式容易记混，建议记住”牺牲一个单元”这个核心思路，公式现场推。

普通数组队列 vs 循环数组队列：入队出队过程详解

先用一个具体例子把两种队列的入队出队过程走一遍，你就明白了。假设数组长度为 5（下标 0~4）。

普通数组队列的入队出队过程：

入队（enqueue）：新元素往队尾（rear）放，放完 rear 往后挪一格。
出队（dequeue）：从队头（front）取元素，取完 front 往后挪一格。

走一遍例子：

初始状态：front=0，rear=0，队列为空 [_, _, _, _, _]
入队 1：放到下标 0，rear=1 → [1, _, _, _, _]
入队 2：放到下标 1，rear=2 → [1, 2, _, _, _]
入队 3：放到下标 2，rear=3 → [1, 2, 3, _, _]
出队：取走下标 0 的 1，front=1 → [_, 2, 3, _, _]
出队：取走下标 1 的 2，front=2 → [_, _, 3, _, _]
入队 4：放到下标 3，rear=4 → [_, _, 3, 4, _]
入队 5：放到下标 4，rear=5 → [_, _, 3, 4, 5]
入队 6：rear=5 已经超出数组边界（最大下标是 4），但前面两个位置是空的！这就是假溢出

看到没？普通数组队列就像一条单行道，front 和 rear 只能往前走，走过的位置就浪费了。

循环数组队列的入队出队过程：

循环队列的核心是”绕圈”——rear 或 front 到达数组末尾后，不是溢出，而是绕到数组开头。用取模运算实现：rear = (rear + 1) % size，front = (front + 1) % size。

同样走一遍例子（数组长度 5，约定牺牲一个单元，所以实际最多存 4 个元素）：

初始状态：front=0，rear=0，队列为空 [_, _, _, _, _]
入队 1：放到下标 0，rear=(0+1)%5=1 → [1, _, _, _, _]
入队 2：放到下标 1，rear=(1+1)%5=2 → [1, 2, _, _, _]
入队 3：放到下标 2，rear=(2+1)%5=3 → [1, 2, 3, _, _]
出队：取走下标 0 的 1，front=(0+1)%5=1 → [_, 2, 3, _, _]
出队：取走下标 1 的 2，front=(1+1)%5=2 → [_, _, 3, _, _]
入队 4：放到下标 3，rear=(3+1)%5=4 → [_, _, 3, 4, _]
入队 5：放到下标 4，rear=(4+1)%5=0 → [_, _, 3, 4, 5]（rear 绕回开头了！）
入队 6：放到下标 0，rear=(0+1)%5=1 → [6, _, 3, 4, 5]（成功利用了前面的空位！）

对比一下：普通数组到第 9 步就卡住了，循环数组却能继续用。这就是循环队列的威力。

为什么要用循环数组实现队列？优点是什么？

用循环数组实现队列，核心目的是解决普通数组队列的”假溢出”问题。

假溢出的意思是：数组的物理空间还没满，但因为队头已经移到了数组末尾，队尾再往后加就超出数组边界了。比如数组长度为 5，依次入队 1,2,3,4,5，数组变成 [1,2,3,4,5]；然后出队两次，数组变成 [_, _, 3,4,5]（front=2）；再想入队 6，队尾 rear=5 已经到数组边界了，但前面两个位置是空的，这就是假溢出。

循环数组的解决方案是把数组看作环形的，rear 到达数组末尾后，下次入队就绕到数组开头（用取模运算实现：rear = (rear+1) % size）。

优点总结（说人话版）：

不浪费空间：前面出队空出来的位置能接着用，不用动不动就扩容或者把所有元素往前挪
写代码简单：就两个指针（front 管队头，rear 管队尾），加个取模运算（%）就能绕圈，没什么复杂逻辑
速度快：入队出队都是一步到位，不像链表还要找指针、分配内存
CPU 读得快：数组在内存里是连在一起的，CPU 能一次性预读好多数据，比链表东一块西一块快多了

代码示例：

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity + 1  
        self.items = [None] * self.capacity
        self.front = 0
        self.rear = 0
    
    def is_empty(self):
        return self.front == self.rear
    
    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front
    
    def enqueue(self, item):
        if self.is_full():
            raise Exception("Queue is full")
        self.items[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
    
    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        item = self.items[self.front]
        self.front = (self.front + 1) % self.capacity
        return item
    
    def size(self):
        return (self.rear - self.front + self.capacity) % self.capacity

注意构造函数里 self.capacity = capacity + 1，这就是”牺牲一个单元”的实现——实际容量比用户要求的多 1，用来区分队满和队空的状态。

用循环队列实现 BFS

队列最典型的应用是广度优先搜索（BFS），下面用我们刚才实现的 CircularQueue 来做一个图的 BFS 遍历示例。

def bfs_with_circular_queue(graph, start, num_nodes):
    visited = [False] * (num_nodes + 1)
    queue = CircularQueue(num_nodes)
    result = []
    
    queue.enqueue(start)
    visited[start] = True
    
    while not queue.is_empty():
        node = queue.dequeue()
        result.append(node)
        
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.enqueue(neighbor)
    
    return result

# 测试：图的邻接表表示
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6],
    4: [2, 7],
    5: [2, 7],
    6: [3],
    7: [4, 5]
}

print(bfs_with_circular_queue(graph, 1, 7))  # [1, 2, 3, 4, 5, 6, 7]

这个例子用循环队列代替了 Python 的 deque，效果完全一样，但能让你看到队列在 BFS 中的核心作用——一层一层地往外扩展。

Python 的 deque 是什么？怎么用？

刚才提到的 deque 是 Python 标准库 collections 模块里的一个数据结构，全称是 “double-ended queue”（双端队列）。它是 Python 官方推荐的队列实现，比自己用列表（list）模拟队列高效得多。

为什么不用 list 做队列？

list 的 append() 在末尾加元素是 O(1)，但 pop(0) 从开头删元素是 O(n)——因为要把后面所有元素往前挪一格
deque 的头尾操作都是 O(1)，专门优化过

deque 的基本用法：

from collections import deque

# 创建 deque
q = deque()              # 空队列
q = deque([1, 2, 3])     # 从列表创建

# 入队（往队尾加）
q.append(4)              # q = deque([1, 2, 3, 4])

# 出队（从队头取）
q.popleft()              # 返回 1，q = deque([2, 3, 4])

# 查看队头（不删除）
q[0]                     # 返回 2

# 队尾操作（deque 特有，普通队列没有）
q.appendleft(0)          # 往队头加，q = deque([0, 2, 3, 4])
q.pop()                  # 从队尾取，返回 4，q = deque([0, 2, 3])

# 常用方法
len(q)                   # 队列长度，返回 3
q.clear()                # 清空队列
q.extend([5, 6])         # 批量入队，q = deque([5, 6])
q.extendleft([4, 3])     # 批量从队头入队（注意顺序），q = deque([3, 4, 5, 6])

deque 在 BFS 中的标准用法：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

记住：在 Python 里写队列，优先用 collections.deque，别用 list 模拟！

树：从二叉树到红黑树

树是层次结构，一对多，像家谱或公司组织架构。重点是二叉树这一支，往上延伸到 B 树和红黑树。

先说二叉树本身，每个节点最多两个子节点。两个常见概念必须分清：满二叉树是”每个节点都有两个子节点，且所有叶子在同一层”，整棵树长得严丝合缝；完全二叉树是”除最后一层外都满，最后一层从左到右连续排”，允许最后一层没排满，但不允许中间有空缺。这两个词看着像，差别就在”满”和”连续”上。

二叉树的遍历是核心中的核心，四种方式要倒背如流：前序（根左右）、中序（左根右）、后序（左右根）、层序（按层从左到右）。前中后指的是根与左右的相对顺序。

一个经典重点是：前序加中序可以唯一确定一棵二叉树，后序加中序也可以，但前序加后序不行。原因是前序和后序都能确定根，但只有中序能区分左右子树。

二叉树四种遍历：用一棵具体的树走一遍

光说”根左右、左根右”容易迷糊，咱们拿一棵具体的二叉树实际走一遍。这棵树长这样（用文字画出来）：

也就是节点 1 是根，左孩子 2、右孩子 3；节点 2 左孩子 4、右孩子 5；节点 3 没有左孩子、右孩子 6；节点 5 左孩子 7、没有右孩子。

前序遍历（根左右）：先访问根，再访问左子树，再访问右子树。

访问 1
进左子树（以 2 为根）：访问 2，进 2 的左子树访问 4（4 是叶子），回来到 2 的右子树（以 5 为根）：访问 5，进 5 的左子树访问 7
进右子树（以 3 为根）：访问 3，3 没有左孩子，进右子树访问 6
结果是 1, 2, 4, 5, 7, 3, 6

中序遍历（左根右）：先访问左子树，再访问根，再访问右子树。

1 的左子树是 2 那一支：先访问 2 的左子树（4），再访问 2，再访问 2 的右子树（5 那一支：先访问 5 的左子树 7，再访问 5）
访问根 1
1 的右子树是 3 那一支：3 没有左子树，访问 3，再访问 3 的右子树（6）
结果是 4, 2, 7, 5, 1, 3, 6

后序遍历（左右根）：先访问左子树，再访问右子树，最后访问根。

1 的左子树（2 那一支）：先访问 4，再访问 2 的右子树（5 那一支：先访问 7，再访问 5），最后访问 2
1 的右子树（3 那一支）：3 没有左子树，访问右子树 6，最后访问 3
最后访问根 1
结果是 4, 7, 5, 2, 6, 3, 1

层序遍历（按层从左到右）：用队列，从根开始一层一层往下。

第 0 层：1
第 1 层：2, 3
第 2 层：4, 5, 6
第 3 层：7
结果是 1, 2, 3, 4, 5, 6, 7

代码写出来对照着看：

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

# 构造上面那棵树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
root.left.right.left = TreeNode(7)

# 前序：根左右
def preorder(node):
    if node is None:
        return []
    return [node.val] + preorder(node.left) + preorder(node.right)

# 中序：左根右
def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)

# 后序：左右根
def postorder(node):
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.val]

# 层序：队列辅助的 BFS
from collections import deque
def levelorder(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)
    return result

print(preorder(root))   # [1, 2, 4, 5, 7, 3, 6]
print(inorder(root))    # [4, 2, 7, 5, 1, 3, 6]
print(postorder(root))  # [4, 7, 5, 2, 6, 3, 1]
print(levelorder(root)) # [1, 2, 3, 4, 5, 6, 7]

把上面四个结果背下来，遇到求某棵树的遍历序列就能照着套。

为什么需要迭代遍历？递归不是更简单吗？

递归遍历写起来确实简单，但有两个致命问题：

问题一：栈溢出风险。递归靠的是系统栈，系统栈的深度有限（通常几千层）。如果二叉树深度很大（比如退化成一条链有几万个节点），递归就会栈溢出。迭代遍历用自己控制的堆内存栈，可以处理任意深度的树。

问题二：性能开销。每一次递归调用都要压栈、保存上下文、弹栈，这些都有开销。迭代遍历虽然代码长，但没有这些额外开销，实际运行更快。

问题三：语言限制。有些语言对尾递归优化支持不好，或者根本不支持递归（比如某些嵌入式环境），这时候只能用迭代。

所以面试题经常考迭代遍历，要考察你对遍历本质的理解——递归只是栈的语法糖，真正的遍历逻辑就是用栈模拟。

这句话怎么理解？举个形象的例子：

你去逛一个大商场（二叉树），商场有很多楼层和店铺（节点）。递归就像你脑子里有个”逛商场指南”，告诉你先逛一层、再逛二层、再逛三层，遇到分叉口就先往左走、再往右走。这个指南帮你自动记住”我刚才逛到哪了，等下要回哪继续逛”，但这个记忆空间（系统栈）是有限的，商场太大你就记不住了。

迭代遍历就是你自己带个笔记本（自己的栈），每到一个分叉口，就把”等下要回来逛的地方”记在本子上。比如你到了一层的分叉口，左边是服装店，右边是电器店，你就先把”电器店”记在本子上，然后去逛服装店；逛完服装店回来，再从本子上翻出”电器店”继续逛。

两种方式逛的路线完全一样，但一个是靠系统帮你记（递归），一个是你自己记（迭代）。面试官想考的就是：你知不知道这个”记路线”的本质，能不能自己动手实现这个笔记本（栈）。

二叉树迭代遍历代码

前序迭代（根左右）：用栈，先访问根，再把右孩子压栈（因为栈后进先出，要让左孩子先出），再压左孩子。

def preorder_iterative(root):
    if root is None:
        return []
    stack = [root]
    result = []
    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):
    if root is None:
        return []
    stack = []
    result = []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
    return result

后序迭代（左右根）：有两种写法。第一种是用两个栈，先按根右左的顺序压栈到 s1，然后弹出到 s2，s2 就是左右根的顺序。第二种是用一个栈加标记。

def postorder_iterative(root):
    if root is None:
        return []
    s1 = [root]
    s2 = []
    while s1:
        node = s1.pop()
        s2.append(node.val)
        if node.left:
            s1.append(node.left)
        if node.right:
            s1.append(node.right)
    return s2[::-1]

验证一下：

1
2
3

print(preorder_iterative(root))   # [1, 2, 4, 5, 7, 3, 6]
print(inorder_iterative(root))    # [4, 2, 7, 5, 1, 3, 6]
print(postorder_iterative(root))  # [4, 7, 5, 2, 6, 3, 1]

和递归结果完全一致。记住一句话：前序是”先访问再压栈”，中序是”先压左再访问再压右”，后序可以用两个栈逆序。

用的多的还是具有特殊性质的二叉树，例如二叉搜索树（BST），它的规则是”左子树都小于根，右子树都大于根”，中序遍历正好得到有序序列。

乱序序列怎么形成 BST？

给定一个乱序序列，怎么把它建成一棵二叉搜索树？有两种常见方法：

方法一：按顺序插入。逐个把元素插入到 BST 中，每次插入都从根开始比较，小于根就往左走，大于根就往右走，找到合适的空位就放进去。

这种方法的缺点是：如果序列本身有序，插入结果会退化成一条链（比如序列 [1,2,3,4,5] 插入后变成右斜链），查找复杂度变成 O(n)。

代码：

def insert_bst(root, val):
    if root is None:
        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 build_bst(nums):
    root = None
    for num in nums:
        root = insert_bst(root, num)
    return root

# 测试：插入 [5,3,7,2,4,6,8]
root = build_bst([5,3,7,2,4,6,8])
# 中序遍历验证：应该是有序的 [2,3,4,5,6,7,8]
print(inorder(root))  # [2, 3, 4, 5, 6, 7, 8]

方法二：选中间元素做根（构建平衡 BST）。为了避免退化，最好的办法是先把序列排序，然后选中间元素做根，左边的元素递归建左子树，右边的元素递归建右子树。这样建成的树是完全平衡的。

def sorted_array_to_bst(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sorted_array_to_bst(nums[:mid])
    root.right = sorted_array_to_bst(nums[mid+1:])
    return root

# 测试：[1,2,3,4,5,6,7]
root = sorted_array_to_bst([1,2,3,4,5,6,7])
# 树结构：
#       4
#     /   \
#    2     6
#   / \   / \
#  1   3 5   7

注意：乱序序列建 BST，结果不是唯一的，取决于插入顺序。但中序遍历结果一定是有序的，这是 BST 的核心性质。

AVL 树：最严格的平衡二叉树

普通 BST 最大的问题是可能退化成一条链。比如依次插入 1,2,3,4,5，BST 变成右斜链，查找复杂度从 O(logn) 退化成 O(n)。AVL 树就是为了解决这个问题而诞生的最早的自平衡二叉搜索树。

平衡的定义：对于树中任意节点，它的左子树和右子树的高度差（平衡因子）不超过 1。这样整棵树的高度就能保证在 O(logn) 范围内。

实现平衡的核心手段是旋转，有四种旋转方式：

左旋（Left Rotation）：右子树太高，把右孩子变成根，原根变成左孩子
右旋（Right Rotation）：左子树太高，把左孩子变成根，原根变成右孩子
左右双旋（Left-Right Rotation）：先对左子树左旋，再整体右旋
右左双旋（Right-Left Rotation）：先对右子树右旋，再整体左旋

旋转的目的是调整节点的位置，让左右子树高度差回到允许范围内，同时保持 BST 的性质（左子树都小于根，右子树都大于根）。

AVL 树的特点（说人话版）：

查得快：因为树长得特别匀称，不会出现”一条腿长一条腿短”的情况，所以找东西总能走最短路径
改得麻烦：每次插入或删除节点后，都要检查”左右两边是不是一样高”，如果不一样高就得”转一转”调整
转得勤：相比红黑树，AVL 树对平衡的要求更严，所以调整的次数也更多

AVL 树的操作方法（说人话版）：

插入：跟普通 BST 一样找到位置插进去，但插完后要从新节点往回走，检查一路上的节点是不是平衡，不平衡就转一转
删除：找到节点删掉，然后也是往回走检查平衡，不平衡就转一转
查找：跟普通 BST 一样，往左找小的，往右找大的

AVL 树 vs 红黑树（形象比喻）：

AVL 树就像一个强迫症患者，家里的东西必须摆得整整齐齐、左右对称，差一点都不行。所以你找东西很快（东西摆得规整），但收拾屋子很累（调整频繁）。

红黑树就比较佛系，差不多整齐就行，不用那么严格对称。所以收拾屋子轻松（调整少），找东西也还行（虽然没那么快但也够用）。

简单总结：

读得多、写得少（比如查字典）：选 AVL，找得快
写得多、读得少（比如频繁更新的排行榜）：选红黑树，改得快

代码示例（AVL 树完整实现）：

class AVLNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def get_height(self, node):
        return node.height if node else 0
    
    def get_balance(self, node):
        return self.get_height(node.left) - self.get_height(node.right) if node else 0
    
    def right_rotate(self, y):
        x = y.left
        T2 = x.right
        
        x.right = y
        y.left = T2
        
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
        
        return x
    
    def left_rotate(self, x):
        y = x.right
        T2 = y.left
        
        y.left = x
        x.right = T2
        
        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        
        return y
    
    def insert(self, node, val):
        if not node:
            return AVLNode(val)
        
        if val < node.val:
            node.left = self.insert(node.left, val)
        else:
            node.right = self.insert(node.right, val)
        
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
        
        balance = self.get_balance(node)
        
        if balance > 1 and val < node.left.val:
            return self.right_rotate(node)
        
        if balance < -1 and val > node.right.val:
            return self.left_rotate(node)
        
        if balance > 1 and val > node.left.val:
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)
        
        if balance < -1 and val < node.right.val:
            node.right = self.right_rotate(node.right)
            return self.left_rotate(node)
        
        return node
    
    def search(self, node, val):
        if not node or node.val == val:
            return node
        if val < node.val:
            return self.search(node.left, val)
        return self.search(node.right, val)

# 测试 AVL 树插入
avl = AVLTree()
root = None
for num in [10, 20, 30, 40, 50, 25]:
    root = avl.insert(root, num)

# 查找测试
print(avl.search(root, 25) is not None)  # True
print(avl.search(root, 100) is not None) # False

B 树：为什么矮胖？为什么适合磁盘？

B 树是一种多路搜索树，它和二叉树的根本区别在于”一个节点可以有多个孩子”。

B 树的结构特点：

一个 m 阶 B 树，每个节点最多有 m 个子节点，最多有 m-1 个关键字
关键字在节点中按升序排列
内部节点的关键字起到”分隔”子树的作用
所有叶子节点在同一层

为什么 B 树是矮胖的？
假设 m=1000（一个节点存 999 个关键字），那么：

第一层（根）：1 个节点，999 个关键字
第二层：最多 1000 个子节点，每个 999 个关键字，共约 100 万个关键字
第三层：最多 1000×1000 个子节点，共约 10 亿个关键字

10 亿条数据只需要 3 层，这就是”矮胖”的原因。

为什么适合磁盘？
磁盘的读取是”按块读取”的，一次 IO 操作会读取一整个磁盘块（通常 4KB 或更大）。如果用二叉搜索树，每个节点只存一个关键字，一次 IO 只能读一个节点，查找 10 亿条数据需要 30 次 IO。而 B 树一次 IO 能读一个完整节点的 999 个关键字，同样的数据只需要 3 次 IO。

这就是 B 树的核心价值：减少磁盘 IO 次数。所以 B 树广泛用于数据库索引（MySQL InnoDB 的 B+树）和文件系统。

红黑树中叶子节点、NIL、无子节点的关系

这是一个很容易混淆的点，记住一句话：在红黑树中，所有真正的叶子节点（没有子节点的节点）都被替换成了 NIL 哨兵节点。

具体来说：

无子节点的节点：指没有左孩子和右孩子的普通节点（比如值为 3 的节点，它没有子节点）
叶子节点（Leaf）：在红黑树的定义中，叶子节点就是 NIL 哨兵节点，它们不存储数据
NIL 哨兵节点：是一种特殊的空节点，颜色为黑色，作为所有无子节点的节点的孩子

举个例子：

     10(黑)
    /    \
   5(红)  15(红)
  / \     / \
NIL NIL NIL NIL

这里 5 和 15 是无子节点的节点，它们的左孩子和右孩子都是 NIL 哨兵节点。在红黑树的定义中，NIL 节点才是真正的叶子节点。

这样设计的好处是：统一处理边界情况，让红黑树的五条性质更容易维护（比如性质五”黑高相同”）。

红黑树五条性质有什么用？不只是定义！

红黑树的五条性质不是随便定的，每一条都有其作用：

性质一：节点非红即黑 → 简化颜色状态，只有两种选择

性质二：根节点是黑 → 根节点是所有路径的起点，设为黑色让黑高计算更统一

性质三：叶子节点（NIL）是黑 → 统一边界，让所有路径的终点都是黑色节点

性质四：红节点的孩子必须是黑 → 防止出现连续两个红节点，保证不会有一条路径全是红节点

性质五：从任一节点到其所有叶子节点的路径，黑节点数量相同（黑高相同） → 这是核心性质！保证了最长路径不超过最短路径的两倍：

最短路径：全是黑节点
最长路径：黑红交替，因为不能有连续两个红，所以最长路径最多是最短路径的 2 倍

这五条性质共同作用，保证了红黑树的高度是 O(logn)，从而实现了高效的查找、插入和删除。

红黑树的实际生活使用场景

除了 Java 的 TreeMap 和 TreeSet，红黑树在实际生活中还有很多应用：

Linux 内核的 CFS 调度器：用红黑树管理进程的虚拟运行时间，实现公平调度
Linux 内核的 epoll：用红黑树管理监听的文件描述符
Redis 的有序集合（ZSet）：底层用跳表，但某些实现也会用到红黑树
数据库索引：虽然主流数据库用 B+树，但在内存索引中红黑树也很常见
编译器的符号表：管理变量和函数的符号信息，需要高效的插入、删除和查找
窗口管理器：管理窗口的层级关系，需要按层级有序遍历

为什么这些场景选择红黑树？

需要有序性：红黑树的中序遍历是有序的
需要高效增删查：O(logn) 的复杂度
需要自平衡：避免退化

二叉树性质公式的高效记忆方法

二叉树有几个常用的性质公式，记起来容易混，这里给一套记忆方法：

公式一：n0 = n2 + 1（叶子节点数 = 度为 2 的节点数 + 1）

记忆方法：想象每个节点都有”伸出的手”，度为 0 的节点（叶子）伸出 0 只手，度为 1 的节点伸出 1 只手，度为 2 的节点伸出 2 只手。总共有 n-1 条边（树的边数 = 节点数 - 1），所以：

0×n0 + 1×n1 + 2×n2 = n-1
又因为 n = n0 + n1 + n2
代入得：n1 + 2n2 = n0 + n1 + n2 - 1
化简：n2 = n0 - 1 → n0 = n2 + 1

公式二：n 个节点的完全二叉树深度为 ⌊log₂n⌋ + 1

记忆方法：完全二叉树第 k 层最多有 2^(k-1) 个节点，前 k 层最多有 2^k - 1 个节点。深度就是最大的 k 满足 2^(k-1) ≤ n < 2^k，取对数就是 k-1 ≤ log₂n < k，所以 k = ⌊log₂n⌋ + 1。

公式三：完全二叉树中，节点 i 的左孩子是 2i+1，右孩子是 2i+2（下标从 0 开始）

记忆方法：想象完全二叉树按层序排列成数组，第 0 层 1 个节点（下标 0），第 1 层 2 个节点（下标 1,2），第 2 层 4 个节点（下标 3-6）。节点 i 的左孩子就是下一层第 2i+1 个位置，右孩子就是第 2i+2 个位置。

公式四：前序 + 中序 = 唯一确定一棵二叉树

记忆方法：前序确定根（第一个元素），中序确定左右子树（根左边是左子树，右边是右子树）。递归下去就能唯一确定。

公式五：满二叉树第 k 层有 2^(k-1) 个节点，总节点数 2^k - 1

记忆方法：满二叉树每一层都是上一层的两倍，等比数列求和。

图：邻接矩阵与邻接表

图是比树更一般的结构，顶点之间的关系是多对多，任意两个点都能连。图分无向图、有向图，边还可以带权。要会区分度、入度、出度：无向图谈度，有向图分开谈入度和出度。

图的存储方式是这一节的重点，两种必须都会。

邻接矩阵是用一个 n×n 的二维数组，matrix[i][j]=1 表示顶点 i 到 j 有边，带权图就把 1 换成权值。它的优点是查边特别快，O(1) 就能判断两点之间有没有边；缺点是空间占用固定 O(n²)，无论边多边少都占这么多。所以邻接矩阵适合稠密图（边特别多的情况）。无向图的邻接矩阵一定是对称的，这是容易混淆的判断点。

邻接表是每个顶点挂一个链表，链表里存它的所有邻居。它的优点是省空间，只存实际存在的边，适合稀疏图；缺点是判断两点之间有没有边要遍历链表，不能一步到位。

对比记忆：稠密用矩阵、稀疏用邻接表。空间上，邻接矩阵 O(n²)，邻接表 O(n+e)（n 是顶点数、e 是边数）。无向图邻接表中所有链表节点数之和是 2e，有向图是 e。

邻接表代码示例

邻接表可以用数组+链表实现，也可以用字典+列表实现。下面是 Python 实现：

from collections import defaultdict

class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed
    
    def add_edge(self, u, v, weight=None):
        self.graph[u].append((v, weight))
        if not self.directed:
            self.graph[v].append((u, weight))
    
    def get_neighbors(self, u):
        return self.graph.get(u, [])
    
    def __repr__(self):
        result = []
        for vertex in sorted(self.graph.keys()):
            neighbors = [f"{v}({w})" if w else str(v) for v, w in self.graph[vertex]]
            result.append(f"{vertex}: {', '.join(neighbors)}")
        return "\n".join(result)

# 无向图示例
g = Graph(directed=False)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 6)
g.add_edge(4, 7)
g.add_edge(5, 7)

print("无向图邻接表：")
print(g)
# 输出：
# 1: 2(None), 3(None)
# 2: 1(None), 4(None), 5(None)
# 3: 1(None), 6(None)
# 4: 2(None), 7(None)
# 5: 2(None), 7(None)
# 6: 3(None)
# 7: 4(None), 5(None)

# 带权有向图示例
wg = Graph(directed=True)
wg.add_edge(1, 2, 5)
wg.add_edge(1, 3, 2)
wg.add_edge(2, 4, 1)
wg.add_edge(3, 4, 7)

print("\n带权有向图邻接表：")
print(wg)
# 输出：
# 1: 2(5), 3(2)
# 2: 4(1)
# 3: 4(7)
# 4:

邻接矩阵代码示例

class GraphMatrix:
    def __init__(self, num_vertices, directed=False):
        self.num_vertices = num_vertices
        self.directed = directed
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
    
    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        if not self.directed:
            self.matrix[v][u] = weight
    
    def has_edge(self, u, v):
        return self.matrix[u][v] != 0
    
    def get_weight(self, u, v):
        return self.matrix[u][v]
    
    def __repr__(self):
        result = ["  " + " ".join(str(i) for i in range(self.num_vertices))]
        for i in range(self.num_vertices):
            row = [str(i)] + [str(x) for x in self.matrix[i]]
            result.append(" ".join(row))
        return "\n".join(result)

# 无向图示例（5 个顶点，下标 0-4）
gm = GraphMatrix(5, directed=False)
gm.add_edge(0, 1)
gm.add_edge(0, 2)
gm.add_edge(1, 3)
gm.add_edge(2, 3)
gm.add_edge(3, 4)

print("无向图邻接矩阵：")
print(gm)
# 输出：
#   0 1 2 3 4
# 0 0 1 1 0 0
# 1 1 0 0 1 0
# 2 1 0 0 1 0
# 3 0 1 1 0 1
# 4 0 0 0 1 0

邻接矩阵和邻接表的实际应用

邻接矩阵的应用场景：

稠密图算法：比如 Floyd-Warshall 算法求任意两点最短路径，需要 O(n³) 时间，用邻接矩阵存图正好匹配这个复杂度
图的传递闭包：判断任意两点是否连通，用邻接矩阵做矩阵乘法很方便
社交网络分析：小范围社交网络（比如一个班级、一个公司），每个人之间的关系都比较密集
图像处理：像素之间的邻接关系，每个像素最多和 4 个或 8 个像素相邻，用邻接矩阵很直观

邻接表的应用场景：

稀疏图算法：比如 Dijkstra、Prim、Kruskal 算法，这些算法的时间复杂度和边数相关，用邻接表可以节省空间
大规模图处理：比如社交网络（Facebook、Twitter），每个用户平均只有几百个好友，图非常稀疏
网页链接分析：搜索引擎的网页链接图，几十亿个网页但每个网页平均只有几十个链接
推荐系统：用户-物品交互图，用户数和物品数都很大但每个用户只和少量物品交互

选择建议：

如果边数 e 接近 n²（稠密图），用邻接矩阵
如果边数 e 远小于 n²（稀疏图），用邻接表
如果需要频繁判断两点之间是否有边，用邻接矩阵（O(1)）
如果需要频繁遍历某个节点的所有邻居，用邻接表（O(度数)）

哈希表：用空间换时间的典范

哈希表是”用空间换时间”这句话的最佳注脚。它通过一个哈希函数，把 key 直接映射到数组下标，所以查找、插入、删除平均都能做到 O(1)，这是其他结构比不了的。

哈希函数最常见的是除留余数法，H(key) = key mod p，其中 p 通常选一个不大于表长的质数。这一步不是重点，重点在冲突处理。

冲突是不可避免的，因为不同的 key 可能算出同一个地址。解决冲突主要有两大流派。第一类是开放定址法，冲突了就去寻找下一个空位，具体有线性探测（往后一个一个找）、二次探测（按平方跳跃着找）。第二类是链地址法，也叫拉链法，把映射到同一地址的所有元素挂成一个链表。两种方法各有特点：开放定址法容易产生”聚集”现象（连续占用一长串），拉链法处理起来直观但要多存指针。

哈希表冲突处理：线性探测和拉链法的具体操作

光说”往后找空位””挂链表”还是抽象，咱们拿一组数实际插一遍。设表长 7，哈希函数 H(key) = key mod 7，插入序列是 15, 8, 1, 22, 16, 9。

先算每个 key 的初始地址：15 mod 7 = 1，8 mod 7 = 1，1 mod 7 = 1，22 mod 7 = 1，16 mod 7 = 2，9 mod 7 = 2。前四个都映射到位置 1，后两个映射到位置 2，冲突很多，正好演示冲突处理。

线性探测法（开放定址法的一种）的规则是：算出地址 a，如果 a 被占了，就看 a+1，再被占就看 a+2，依此类推，找到第一个空位就放进去（超过表尾要回绕）。

按这个规则插入：

插 15：地址 1，位置 1 空，直接放。表变成 [_, 15, _, _, _, _, _]
插 8：地址 1，位置 1 有 15，看位置 2，空，放 8。表变成 [_, 15, 8, _, _, _, _]
插 1：地址 1，位置 1 有 15，位置 2 有 8，位置 3 空，放 1。表变成 [_, 15, 8, 1, _, _, _]
插 22：地址 1，位置 1、2、3 都被占，位置 4 空，放 22。表变成 [_, 15, 8, 1, 22, _, _]
插 16：地址 2，位置 2 有 8，位置 3 有 1，位置 4 有 22，位置 5 空，放 16。表变成 [_, 15, 8, 1, 22, 16, _]
插 9：地址 2，位置 2、3、4、5 都被占，位置 6 空，放 9。表变成 [_, 15, 8, 1, 22, 16, 9]

最终线性探测的结果是 [空, 15, 8, 1, 22, 16, 9]。注意看位置 1 到位置 6 连成一片，这就是”聚集”现象——后面插进来的元素探测距离越来越长，性能变差。

拉链法（链地址法）的规则是：算出地址 a，如果 a 这个位置已经有元素，就把新元素挂到 a 的链表末尾。

按这个规则插入：

插 15：地址 1，链表空，挂上。位置 1：15 -> null
插 8：地址 1，已经有 15，挂到链表尾。位置 1：15 -> 8 -> null
插 1：地址 1，链表是 15->8，挂尾。位置 1：15 -> 8 -> 1 -> null
插 22：地址 1，挂尾。位置 1：15 -> 8 -> 1 -> 22 -> null
插 16：地址 2，位置 2 链表空，挂上。位置 2：16 -> null
插 9：地址 2，已经有 16，挂尾。位置 2：16 -> 9 -> null

最终拉链法的结果是位置 1 挂着 15->8->1->22，位置 2 挂着 16->9，其它位置空。拉链法没有聚集问题，但代价是每个元素要多存一个 next 指针。

查找时也一样：算出地址后，线性探测要顺着往后找直到找到目标或遇到空位（说明不存在）；拉链法只要顺着链表往下找就行。这一组示例搞懂了，要算某个元素的探测次数或查找长度，照着模拟就行。

一个重点知识是装填因子（也叫负载因子），它等于元素个数除以表长。装填因子越大，冲突概率越高、性能越差，所以一般要控制在一定阈值以下，超了就扩容 rehash。

还有一个常见的题型是算平均查找长度（ASL），在给定哈希表和冲突解决方式后，求成功查找和失败查找的 ASL。这类题没有捷径，要把每个元素的探测次数老老实实数出来再求平均，做两三道题就熟练了。

排序三剑客：快排、归并、堆排

排序算法里，重点盯这三个，因为它们都做到了平均 O(nlogn) 这一档，但实现思路和特性完全不同。

快速排序的核心是”分治加基准”。随便选一个元素做基准（pivot），把数组重排成”比基准小的都在左、比基准大的都在右”，这一步叫 partition，然后对左右两段递归做同样的事。快排的平均时间复杂度是 O(nlogn)，最坏情况是 O(n²)，最坏发生在数组已经有序、基准每次都选到最值的时候。快排是原地排序，但它不稳定——相等的元素在分区后相对顺序可能改变。记忆关键：快排”先分区后递归”，分区是它的灵魂。

快速排序的 partition 过程

partition 是快排的灵魂，咱们把这一步单独拆开走一遍。这里用最经典的 Lomuto 写法：选数组最右边的元素做 pivot，用一个指针 i 记录”小于等于 pivot 的区域”的右边界，另一个指针 j 从左往右扫，遇到比 pivot 小的就把它换到左边区域里。

具体步骤：

第一步，选 pivot = nums[right]，初始化 i = left - 1（i 表示”小于等于 pivot 区域”目前是空的）。
第二步，j 从 left 扫到 right-1：

如果 nums[j] <= pivot，就把 i 加 1，然后交换 nums[i] 和 nums[j]（把这个小元素塞进左区域）
如果 nums[j] > pivot，啥也不做，j 继续走
第三步，扫完后，把 pivot 放到中间位置：交换 nums[i+1] 和 nums[right]。
第四步，返回 i+1，这就是 pivot 最终所在的下标。此时 pivot 左边都小于等于它，右边都大于它。

代码：

def partition(nums, left, right):
    pivot = nums[right]      # 选最右边做基准
    i = left - 1             # "小于等于 pivot 区域"的右边界
    for j in range(left, right):
        if nums[j] <= pivot:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]  # 小的换到左边
    nums[i+1], nums[right] = nums[right], nums[i+1]  # pivot 归位
    return i + 1             # 返回 pivot 最终位置

def quickSort(nums, left, right):
    if left < right:
        p = partition(nums, left, right)
        quickSort(nums, left, p - 1)   # 排左半段
        quickSort(nums, p + 1, right)  # 排右半段

输入输出示例。对数组 [5, 2, 8, 3, 9, 1, 7] 做一次 partition（left=0, right=6），pivot = nums[6] = 7：

初始 i = -1
j=0：nums[0]=5 <= 7，i=0，交换 nums[0] 和 nums[0]（自己换自己），数组不变 [5, 2, 8, 3, 9, 1, 7]
j=1：nums[1]=2 <= 7，i=1，交换 nums[1] 和 nums[1]，不变
j=2：nums[2]=8 > 7，跳过
j=3：nums[3]=3 <= 7，i=2，交换 nums[2] 和 nums[3]，数组变成 [5, 2, 3, 8, 9, 1, 7]
j=4：nums[4]=9 > 7，跳过
j=5：nums[5]=1 <= 7，i=3，交换 nums[3] 和 nums[5]，数组变成 [5, 2, 3, 1, 9, 8, 7]
扫完，交换 nums[i+1]=nums[4] 和 nums[right]=nums[6]，也就是交换 9 和 7，数组变成 [5, 2, 3, 1, 7, 8, 9]
返回 i+1 = 4

partition 后，pivot 7 停在下标 4，左边 [5, 2, 3, 1] 都小于等于 7，右边 [8, 9] 都大于 7。然后 quickSort 再对 [5, 2, 3, 1] 和 [8, 9] 分别做同样的 partition，递归下去就排好了。

记住一句话：partition 的核心就是”用 i 划出小于等于区，j 扫一遍把小的塞进去，最后把 pivot 摆到中间”。

完整快排代码（含调用示例）：

def quickSort(nums):
    def partition(left, right):
        pivot = nums[right]
        i = left - 1
        for j in range(left, right):
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[i+1], nums[right] = nums[right], nums[i+1]
        return i + 1
    
    def _quickSort(left, right):
        if left < right:
            p = partition(left, right)
            _quickSort(left, p - 1)
            _quickSort(p + 1, right)
    
    _quickSort(0, len(nums) - 1)
    return nums

# 测试
nums = [5, 2, 8, 3, 9, 1, 7]
print(quickSort(nums.copy()))  # [1, 2, 3, 5, 7, 8, 9]

归并排序完整代码

归并排序也是分治，但思路相反，是”先递归后合并”。它先把数组一直二分到单个元素，然后两两合并成有序段，合并时利用两个有序段首元素比较来归并。归并的时间复杂度是 O(nlogn)，而且最好、最坏、平均都一样，非常稳定；它也是这三个里唯一的稳定排序；代价是需要 O(n) 的额外空间。对比快排和归并，记一句话：”快排先分后治、归并先治后合；快排原地不稳定、归并稳定费空间”。

def mergeSort(nums):
    if len(nums) <= 1:
        return nums
    
    mid = len(nums) // 2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    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

# 测试
nums = [5, 2, 8, 3, 9, 1, 7]
print(mergeSort(nums))  # [1, 2, 3, 5, 7, 8, 9]

输入输出示例。对数组 [5, 2, 8, 3, 9, 1, 7] 做归并排序：

第一层递归：分成 [5, 2, 8] 和 [3, 9, 1, 7]
第二层递归：[5, 2, 8] 分成 [5] 和 [2, 8]；[3, 9, 1, 7] 分成 [3, 9] 和 [1, 7]
第三层递归：[2, 8] 分成 [2] 和 [8]；[3, 9] 分成 [3] 和 [9]；[1, 7] 分成 [1] 和 [7]
合并阶段：[2] 和 [8] 合并成 [2, 8]；[5] 和 [2, 8] 合并成 [2, 5, 8]；[3] 和 [9] 合并成 [3, 9]；[1] 和 [7] 合并成 [1, 7]；[3, 9] 和 [1, 7] 合并成 [1, 3, 7, 9]；最后 [2, 5, 8] 和 [1, 3, 7, 9] 合并成 [1, 2, 3, 5, 7, 8, 9]

记住一句话：归并排序的核心是”先拆到单个元素，再两两合并，合并时用双指针比较首元素”。

堆排序完整代码

堆排序靠的是”堆”这个数据结构。堆是一棵完全二叉树，大顶堆满足父节点大于等于子节点，小顶堆反过来。排序过程是：先把整个数组建成大顶堆，然后把堆顶（最大值）和数组末尾交换，再把剩下的部分重新调整为堆，如此反复，每次取出一个最大值放到末尾。堆排序时间复杂度 O(nlogn)，原地排序，但不稳定。堆的数组表示里有个常用公式：下标从 0 开始时，节点 i 的左孩子是 2i+1、右孩子是 2i+2、父节点是 (i-1)/2，这个一定要记牢，堆排和 TopK 问题都要用。

def heapSort(nums):
    n = len(nums)
    
    def heapify(i, heap_size):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        if left < heap_size and nums[left] > nums[largest]:
            largest = left
        if right < heap_size and nums[right] > nums[largest]:
            largest = right
        if largest != i:
            nums[i], nums[largest] = nums[largest], nums[i]
            heapify(largest, heap_size)
    
    for i in range(n // 2 - 1, -1, -1):
        heapify(i, n)
    
    for i in range(n - 1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        heapify(0, i)
    
    return nums

# 测试
nums = [5, 2, 8, 3, 9, 1, 7]
print(heapSort(nums.copy()))  # [1, 2, 3, 5, 7, 8, 9]

输入输出示例。对数组 [5, 2, 8, 3, 9, 1, 7] 做堆排序：

建堆阶段：从最后一个非叶子节点（下标 2）开始，依次做 heapify
- i=2（元素 8）：左右孩子都超出范围，无需调整
- i=1（元素 2）：左孩子 3、右孩子 9，最大是 9，交换 2 和 9，数组变成 [5, 9, 8, 3, 2, 1, 7]，继续对下标 4 做 heapify（无需调整）
- i=0（元素 5）：左孩子 9、右孩子 8，最大是 9，交换 5 和 9，数组变成 [9, 5, 8, 3, 2, 1, 7]，继续对下标 1 做 heapify
  - i=1（元素 5）：左孩子 3、右孩子 2，最大是 5，无需调整
- 建堆完成，数组是 [9, 5, 8, 3, 2, 1, 7]，对应的大顶堆：
  1
  2
  3
  4
  5
  9
  / \
  5 8
  / \ / \
  3 2 1 7
排序阶段：每次把堆顶和末尾交换，缩小堆范围，对新堆顶做 heapify
- 交换 9 和 7 → [7, 5, 8, 3, 2, 1, 9]，heapify(0, 6) → [8, 5, 7, 3, 2, 1, 9]
- 交换 8 和 1 → [1, 5, 7, 3, 2, 8, 9]，heapify(0, 5) → [7, 5, 1, 3, 2, 8, 9]
- 交换 7 和 2 → [2, 5, 1, 3, 7, 8, 9]，heapify(0, 4) → [5, 3, 1, 2, 7, 8, 9]
- 交换 5 和 3 → [2, 3, 1, 5, 7, 8, 9]，heapify(0, 3) → [3, 2, 1, 5, 7, 8, 9]
- 交换 3 和 1 → [1, 2, 3, 5, 7, 8, 9]，heapify(0, 2) → [2, 1, 3, 5, 7, 8, 9]
- 交换 2 和 1 → [1, 2, 3, 5, 7, 8, 9]，排序完成

记住一句话：堆排序的核心是”先建大顶堆，再反复把堆顶交换到末尾并调整”。

**建堆的时间复杂度是 O(n)**，不是 O(nlogn)，因为越往上的节点越少、下沉距离越短，平均下来是线性的。这个结论是建堆过程的标志性重点，记一下。

下面用一个小例子手动走一遍建堆过程：

对数组 [4, 1, 3, 2] 建大顶堆，n=4，最后一个非叶子节点下标是 4//2-1 = 1：

初始数组 [4, 1, 3, 2]，对应的树是：

i=1（节点 1）：左孩子 nums[3]=2，右孩子没有。2 > 1，最大是 left=3，交换 nums[1] 和 nums[3]，数组变成 [4, 2, 3, 1]。继续对下标 3 做 heapify，但 3 的左孩子 2*3+1=7 超出 n=4，停止。
i=0（节点 4）：左孩子 nums[1]=2，右孩子 nums[2]=3。三者 4、2、3 里 4 最大，largest 还是 0，不交换，停止。

最终建好的大顶堆是 [4, 2, 3, 1]，对应的树是：

每个父节点都大于等于它的孩子，建堆完成。建好堆之后，排序就是反复”把堆顶（最大值）和末尾交换、缩小堆的范围、对新堆顶做 heapify”。比如把 4 换到末尾变成 [1, 2, 3, 4]，对下标 0 做 heapify（堆大小变成 3），3 上浮到堆顶得到 [3, 2, 1, 4]，再把 3 换到下标 2……如此反复直到排好。

这一节的核心重点就三个：稳定性、时间复杂度、空间复杂度。稳定性上记”快排堆排不稳、归并稳”；时间上记”快排最坏 n²、归并堆排都 nlogn 稳如老狗”；空间上记”归并要 O(n) 额外空间，快排堆排原地”。再补一个常见应用：TopK 问题（找前 K 大或前 K 小）用堆做最高效，维护一个大小为 K 的堆即可。

查找：二分与哈希

查找这一块重点两种，对应两种思路。

二分查找要满足一个前提：序列必须有序。它的思路是每次取中间元素和目标比，相等就找到，不等就砍掉一半继续找，时间复杂度 O(logn)。二分查找的坑全在边界上，循环条件是 left<=right 还是 left<right，更新是 left=mid+1 还是 left=mid，取决于你用的是”左闭右闭”还是”左闭右开”区间，选定一种写法就一直用，别来回切。二分还有几个变形很常见：找第一个等于 target 的位置、找最后一个等于 target 的位置、找第一个大于等于 target 的位置，这些变形比基础二分更容易让人混淆。

二分查找：左闭右闭区间完整代码

下面给出最常见的”左闭右闭”写法，顺便讲清楚每个边界为什么这么处理。所谓左闭右闭，就是搜索区间是 [left, right]，left 和 right 都算在区间里。基于这个定义，所有边界处理都有明确含义。

def binarySearch(nums, target):
    left = 0
    right = len(nums) - 1   # 右闭，所以 right 初始化成最后一个下标
    while left <= right:    # 区间里至少还有一个元素就要继续找
        mid = left + (right - left) // 2  # 防止 (left+right) 溢出
        if nums[mid] == target:
            return mid      # 找到，返回下标
        elif nums[mid] < target:
            left = mid + 1   # target 在右半段，mid 已经确认不是答案，排除掉
        else:
            right = mid - 1  # target 在左半段，mid 已经确认不是答案，排除掉
    return -1                # 没找到

边界处理解释：

第一，循环条件为什么是 left <= right 而不是 left < right？因为区间是闭的 [left, right]，当 left == right 时区间里还有一个元素 nums[left] 没查过，必须再进一轮循环查它。如果用 left < right，就会漏掉最后一个元素。

第二，更新时为什么是 left = mid + 1 和 right = mid - 1，而不是 left = mid？因为 nums[mid] 已经确认不等于 target（否则上一行就 return 了），所以 mid 这个位置可以安全排除掉，下一次搜索区间是 [mid+1, right] 或 [left, mid-1]。如果写成 left = mid，在 left 和 right 相邻时就可能死循环（mid 取整后还是 left）。

第三，mid 的计算用 left + (right - left) // 2 而不是 (left + right) // 2，是为了防止 left+right 在某些语言里溢出（Python 不会溢出，但这是通用写法，养成习惯）。

输入输出示例。在有序数组 [1, 3, 5, 7, 9, 11, 13] 里找 target = 7：

left=0, right=6, mid=3, nums[3]=7 == 7，返回 3

找 target = 4（不在数组里）：

left=0, right=6, mid=3, nums[3]=7 > 4, right=2
left=0, right=2, mid=1, nums[1]=3 < 4, left=2
left=2, right=2, mid=2, nums[2]=5 > 4, right=1
left=2, right=1, left > right，退出循环，返回 -1

哈希查找前面哈希表那节已经讲过，平均 O(1)，优势是无序也能查，劣势是冲突会影响性能、且不支持范围查询和有序遍历。两者对比：有序且查找频繁用二分，等值查找为主、不要求有序用哈希。

图遍历：BFS与DFS

图的两种遍历方式必须分清，它们用的辅助结构不同、应用场景也不同。

BFS 是广度优先搜索，思路是从起点出发，一层一层地往外扩，像往水里丢石子泛起的水波纹。它靠队列实现：起点入队，每次出队一个顶点，把它所有未访问的邻居入队，循环到队空。BFS 的特点是”层层推进”，所以它能用来求无权图的最短路径，也能做二叉树的层序遍历。

DFS 是深度优先搜索，思路是从起点出发，一条路走到底走不动了再回退换路，像走迷宫一直贴着墙走到死胡同才回头。它靠递归（本质是栈）或显式栈实现。DFS 适合连通性判断、拓扑排序、找所有解、环检测这类问题。

两者对比记忆：BFS 用队列、DFS 用栈或递归；BFS 找最短路径、DFS 找所有路径或判断连通。时间复杂度上，用邻接表存储时都是 O(V+E)（V 是顶点数、E 是边数），用邻接矩阵时是 O(V²)。这个复杂度对比是重点知识。

图的 BFS 和 DFS：用一个具体的图走一遍

光说”一层层扩””走到底再回退”还是抽象，咱们拿一个具体的无向图实际遍历一次。图长这样：

边有这些：1-2、1-3、2-4、2-5、3-6、4-7、5-7。这是个无向图，每条边双向都通。用邻接表表示（每个顶点的邻居按编号从小到大排）：

1 的邻居：2, 3
2 的邻居：1, 4, 5
3 的邻居：1, 6
4 的邻居：2, 7
5 的邻居：2, 7
6 的邻居：3
7 的邻居：4, 5

先做 BFS，从顶点 1 开始，用队列，每次出队一个顶点就把它的未访问邻居入队：

起点入队，队列=[1]，已访问={1}，输出=[]
出队 1，输出=[1]，邻居 [2, 3] 都没访问，入队。队列=[2, 3]，已访问={1,2,3}
出队 2，输出=[1, 2]，邻居 [1, 4, 5]，1 已访问，4 和 5 入队。队列=[3, 4, 5]，已访问={1,2,3,4,5}
出队 3，输出=[1, 2, 3]，邻居 [1, 6]，1 已访问，6 入队。队列=[4, 5, 6]，已访问+={6}
出队 4，输出=[1, 2, 3, 4]，邻居 [2, 7]，2 已访问，7 入队。队列=[5, 6, 7]，已访问+={7}
出队 5，输出=[1, 2, 3, 4, 5]，邻居 [2, 7] 都已访问，不入队。队列=[6, 7]
出队 6，输出=[1, 2, 3, 4, 5, 6]，邻居 [3] 已访问。队列=[7]
出队 7，输出=[1, 2, 3, 4, 5, 6, 7]，邻居 [4, 5] 都已访问。队列=[]
队空，结束。BFS 结果：1, 2, 3, 4, 5, 6, 7

你看 BFS 的特点是按距离起点 1 的层数访问：第 0 层是 1，第 1 层是 2 和 3，第 2 层是 4、5、6，第 3 层是 7。这就是”层层推进”。

再做 DFS，从顶点 1 开始，用递归（每个顶点访问后立刻递归访问它第一个未访问的邻居）：

访问 1，输出=[1]，邻居 [2, 3]，先递归 2
访问 2，输出=[1, 2]，邻居 [1, 4, 5]，1 已访问，递归 4
访问 4，输出=[1, 2, 4]，邻居 [2, 7]，2 已访问，递归 7
访问 7，输出=[1, 2, 4, 7]，邻居 [4, 5]，4 已访问，递归 5
访问 5，输出=[1, 2, 4, 7, 5]，邻居 [2, 7] 都已访问，回溯
回到 7，邻居都访问完，回溯
回到 4，邻居都访问完，回溯
回到 2，邻居都访问完，回溯
回到 1，邻居 [2, 3] 里 2 已访问，递归 3
访问 3，输出=[1, 2, 4, 7, 5, 3]，邻居 [1, 6]，1 已访问，递归 6
访问 6，输出=[1, 2, 4, 7, 5, 3, 6]，邻居 [3] 已访问，回溯
回到 3，回溯
回到 1，邻居都访问完，结束

DFS 结果：1, 2, 4, 7, 5, 3, 6。可以看到 DFS 是”一条路走到黑再回头”，先把 1->2->4->7->5 这一条路走到底，再回头走 3->6 这一支。

代码对照着看：

from collections import deque, defaultdict

# 构造图
graph = defaultdict(list)
edges = [(1,2), (1,3), (2,4), (2,5), (3,6), (4,7), (5,7)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
# 邻居排序，保证访问顺序确定
for v in graph:
    graph[v].sort()

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

def dfs(graph, start):
    visited = set()
    result = []
    def _dfs(node):
        visited.add(node)
        result.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                _dfs(neighbor)
    _dfs(start)
    return result

print(bfs(graph, 1))  # [1, 2, 3, 4, 5, 6, 7]
print(dfs(graph, 1))  # [1, 2, 4, 7, 5, 3, 6]

注意 BFS 要在入队时立刻标记 visited（防止同一个顶点被重复入队），DFS 在递归入口标记 visited。这是个容易写错的地方，记住”入队即标记”。

BFS 求无权图的最短路径

BFS 的核心价值之一是求无权图的最短路径。因为 BFS 是层层推进的，第一次到达某个节点时走过的步数就是最短路径。

思路：用 parent 字典记录每个节点是从哪个节点来的，BFS 结束后从终点回溯到起点，再反转就是最短路径。

def bfs_shortest_path(graph, start, end):
    visited = {start}
    queue = deque([(start, [start])])
    
    while queue:
        node, path = queue.popleft()
        if node == end:
            return path
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None

# 测试：从 1 到 7 的最短路径
print(bfs_shortest_path(graph, 1, 7))  # [1, 2, 4, 7] 或 [1, 2, 5, 7]

输入输出示例。在上面的图中求从 1 到 7 的最短路径：

第 0 层：队列=[(1, [1])]
第 1 层：出队 1，入队 (2, [1,2]), (3, [1,3])
第 2 层：出队 2，入队 (4, [1,2,4]), (5, [1,2,5])；出队 3，入队 (6, [1,3,6])
第 3 层：出队 4，发现邻居 7 未访问，入队 (7, [1,2,4,7])
出队 7 时，7 == end，返回路径 [1, 2, 4, 7]

路径长度是 3（经过 3 条边），这确实是最短路径。

DFS 的常见应用

DFS 适合”一条路走到底”的场景，下面介绍四个经典应用。

应用一：连通性判断

判断图中两个节点是否连通，或者统计连通分量的数量。

def is_connected(graph, start, end):
    visited = set()
    
    def _dfs(node):
        if node == end:
            return True
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited and _dfs(neighbor):
                return True
        return False
    
    return _dfs(start)

def count_connected_components(graph):
    visited = set()
    count = 0
    
    for node in graph:
        if node not in visited:
            count += 1
            stack = [node]
            visited.add(node)
            while stack:
                curr = stack.pop()
                for neighbor in graph[curr]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        stack.append(neighbor)
    
    return count

# 测试
print(is_connected(graph, 1, 7))  # True
print(is_connected(graph, 1, 8))  # False（8 不在图中）

应用二：拓扑排序

拓扑排序是对有向无环图（DAG）的顶点进行排序，使得对于每条有向边 u->v，u 在排序中都出现在 v 之前。

拓扑排序有两种实现方法：Kahn 算法（基于 BFS 的入度法）和 DFS 后序逆序法。

方法一：Kahn 算法（BFS 入度法）

思路：用入度表记录每个节点的入度，把入度为 0 的节点入队，依次弹出并减少其邻居的入度，重复直到队空。

def topological_sort_kahn(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1
    
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(result) != len(in_degree):
        return None
    
    return result

方法二：DFS 后序逆序法

思路：用 DFS 遍历，先递归访问所有子节点，再把当前节点加入结果列表（后序），最后反转整个列表得到拓扑序。

def topological_sort_dfs(graph):
    visited = set()
    rec_stack = set()
    result = []
    
    def _dfs(node):
        if node in rec_stack:
            return False
        if node in visited:
            return True
        
        visited.add(node)
        rec_stack.add(node)
        
        for neighbor in graph.get(node, []):
            if not _dfs(neighbor):
                return False
        
        rec_stack.remove(node)
        result.append(node)
        return True
    
    for node in graph:
        if node not in visited:
            if not _dfs(node):
                return None
    
    return result[::-1]

# 测试：课程依赖关系（有向图）
course_graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': [],
    'E': ['C']
}
print(topological_sort_kahn(course_graph))    # ['A', 'E', 'B', 'C', 'D'] 或其他合法顺序
print(topological_sort_dfs(course_graph))     # ['E', 'A', 'B', 'C', 'D'] 或其他合法顺序

两种方法的对比：Kahn 算法用队列，DFS 法用栈；Kahn 算法能顺便检测环（结果长度不等于节点数），DFS 法在递归过程中检测环。

应用三：找所有路径

找出从起点到终点的所有路径，这在回溯类问题中非常常见。

def find_all_paths(graph, start, end):
    visited = set()
    paths = []
    
    def _dfs(node, path):
        visited.add(node)
        if node == end:
            paths.append(path.copy())
            visited.remove(node)
            return
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                path.append(neighbor)
                _dfs(neighbor, path)
                path.pop()
        
        visited.remove(node)
    
    _dfs(start, [start])
    return paths

# 测试：找从 1 到 7 的所有路径
print(find_all_paths(graph, 1, 7))
# [[1, 2, 4, 7], [1, 2, 5, 7]]

应用四：环检测

检测图中是否存在环，分为无向图和有向图两种情况。

def has_cycle_undirected(graph):
    visited = set()
    
    def _dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if _dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False
    
    for node in graph:
        if node not in visited and _dfs(node, None):
            return True
    return False

def has_cycle_directed(graph):
    visited = set()
    rec_stack = set()
    
    def _dfs(node):
        if node not in visited:
            visited.add(node)
            rec_stack.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited and _dfs(neighbor):
                    return True
                elif neighbor in rec_stack:
                    return True
        if node in rec_stack:
            rec_stack.remove(node)
        return False
    
    for node in graph:
        if _dfs(node):
            return True
    return False

# 测试
cycle_graph = {1: [2], 2: [3], 3: [1]}
print(has_cycle_undirected(cycle_graph))  # True
print(has_cycle_directed(course_graph))   # False（课程图无环）

无向图检测环的关键是：遇到已访问的节点且不是父节点，说明有环；有向图检测环需要额外用递归栈记录当前路径。

动态规划与贪心：看似像实则不同

这两个算法长得像，都涉及”做选择”，但内核完全不同，是最喜欢拿来对比的一对。

动态规划（DP）的核心思想是把大问题拆成子问题，当子问题有重叠时，把每个子问题的结果记下来避免重复计算。能用 DP 的问题必须满足两个性质：最优子结构（大问题的最优解由子问题的最优解构成）和重叠子问题。做题的关键是写出状态转移方程，也就是”当前状态怎么从前面的状态推过来”。经典例子有斐波那契数列、背包问题（01 背包和完全背包）、最长公共子序列、最长上升子序列、编辑距离。DP 一般是自底向上递推，能保证全局最优，代价是时间和空间都不小（空间往往可以用”滚动数组”优化）。

贪心算法的思路是每一步都选”当前看起来最好”的选项，不回头、不后悔。它不保证全局最优，只有在问题具有”贪心选择性质”时才是正确的。典型例子有活动选择问题（按结束时间排序选最多不冲突活动）、Huffman 编码、最小生成树的 Prim 和 Kruskal 算法、部分背包问题（可分割的背包）。贪心一般效率高、实现简单，但适用面窄。

两者的根本区别要记牢：DP 是”全局考虑、自底向上、保证最优但慢”；贪心是”局部选择、不回头、快但不一定最优”。判断一道题该用哪个，可以先想”贪心能不能成立”——如果每一步的局部最优确实能推出全局最优，就用贪心；如果不行、需要枚举所有子问题的组合，就用 DP。一个简单的判别信号：背包问题里，物品可分割（部分背包）用贪心，物品不可分割（01 背包）用 DP，这个对比非常典型。

动态规划状态转移方程：斐波那契和 01 背包

状态转移方程是 DP 的灵魂，说白了就是”当前状态怎么从前面的状态推过来”。咱们用两个最经典的例子把它写明白。

第一个例子，斐波那契数列。斐波那契数列的定义是：第 0 项是 0，第 1 项是 1，从第 2 项开始每一项等于前两项之和。这就是天然的”当前状态由前面状态推过来”。

状态定义：dp[i] 表示第 i 个斐波那契数
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
边界条件：dp[0] = 0，dp[1] = 1
计算顺序：从 i=2 递推到 i=n

代码：

def fib(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]   # 状态转移方程
    return dp[n]

输入 n=10，输出 55。验算一下：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55，第 10 项确实是 55。

这里”重叠子问题”特别明显：算 fib(5) 要用 fib(4) 和 fib(3)，算 fib(4) 又要用 fib(3) 和 fib(2)，fib(3) 被算了两次。朴素递归会重复算很多次，DP 把每个 fib(i) 算一次存起来，这就是 DP 的价值。

第二个例子，01 背包问题。有 n 个物品，每件有重量 w[i] 和价值 v[i]，背包容量是 W，每件物品要么装要么不装（不能分割），求能装出的最大价值。

状态定义：dp[i][j] 表示”前 i 件物品、背包容量为 j 时能装的最大价值”
状态转移方程（对第 i 件物品，i 从 1 开始数）：
- 不装第 i 件：dp[i][j] = dp[i-1][j]
- 装第 i 件（前提是 j >= w[i-1]，能装得下）：dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1]
- 取两者较大值：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
边界条件：dp[0][j] = 0（没有物品可装，价值为 0）
计算顺序：i 从 1 到 n，j 从 0 到 W

注意下标对应：代码里物品编号从 0 开始，所以第 i 件物品（i 从 1 数）的重量是 w[i-1]、价值是 v[i-1]。

代码：

def knapsack01(w, v, W):
    n = len(w)
    # dp[i][j]：前 i 件物品、容量 j 时的最大价值
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            dp[i][j] = dp[i-1][j]  # 不装第 i 件
            if j >= w[i-1]:        # 能装得下才考虑装
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1])
    return dp[n][W]

输入示例：w = [2, 3, 4, 5]，v = [3, 4, 5, 6]，W = 5。也就是四件物品，重量分别是 2、3、4、5，价值分别是 3、4、5、6，背包容量 5。

走一遍：容量 5 能装的组合有”装第 1 件和第 2 件”（重量 2+3=5，价值 3+4=7）、”装第 3 件”（重量 4，价值 5）、”装第 4 件”（重量 5，价值 6）。最大价值是 7。

代码跑出来 dp[4][5] = 7，结果对得上。这个状态转移方程的核心是”每件物品面临装或不装两个选择”，所以叫 01 背包（0 不装、1 装）。如果是完全背包（每件物品可以装无限件），状态转移方程会变成 dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]] + v[i-1])，注意第二个是 dp[i] 不是 dp[i-1]，因为同一件物品可以重复装。

数据结构与算法知识速记

数组和链表的取舍不要记反：数组查得快 O(1)、增删慢 O(n)；链表查得慢 O(n)、增删快 O(1)。栈是 LIFO，经典应用括号匹配和表达式求值；队列是 FIFO，循环队列判空用 front==rear、判满牺牲一个单元用 (rear+1)%size==front，解决假溢出问题。给定入栈序列判断出栈序列合法性用模拟法，合法数量遵循卡特兰数。BFS 用队列实现，层层推进找最短路径。

满二叉树和完全二叉树一字之差，”满”要求所有层都满，”完全”允许最后一层不满但必须从左连续。二叉树遍历里，前序加中序、后序加中序都能唯一确定一棵树，但前序加后序不行。递归遍历简洁但有栈溢出风险，迭代遍历用栈模拟更安全。乱序序列建 BST 有两种方法：按顺序插入（可能退化）和选中间元素递归构建（平衡）。

AVL 树最严格平衡，平衡因子不超过 1，靠四种旋转（左旋、右旋、左右双旋、右左双旋）维护平衡，查多用 AVL。B 树矮胖是为了减少磁盘 IO，一个节点存多个关键字，适合数据库索引和文件系统。红黑树最长路径不超过最短路径两倍，五条性质共同作用保证 O(logn) 复杂度，其中性质四”红节点孩子必黑”和性质五”黑高相同”最关键。红黑树中叶子节点就是 NIL 哨兵节点，无子节点的节点的孩子都是 NIL。红黑树实际应用包括 Linux CFS 调度器、epoll、编译器符号表等。二叉树性质公式：n0=n2+1（叶子数=度为2的节点数+1），完全二叉树深度⌊log₂n⌋+1。

图的存储上，稠密图用邻接矩阵（查边 O(1)）、稀疏图用邻接表（省空间 O(n+e)），无向图邻接矩阵对称。哈希表冲突处理两大流派，开放定址法有聚集问题、拉链法多存指针，装填因子越大性能越差。排序稳定性口诀”快排堆排不稳、归并稳”，快排最坏 n²、归并和堆排三种复杂度都是 nlogn，归并要 O(n) 额外空间，堆排建堆 O(n)。二分查找的坑在区间边界，选定左闭右闭或左闭右开就别再切。

图遍历中 BFS 配队列、DFS 配栈或递归，邻接表下两者都是 O(V+E)。BFS 层层推进求无权图最短路径，DFS 适合连通性判断、拓扑排序（Kahn 法和 DFS 后序逆序法）、找所有路径、环检测（无向图看父节点，有向图用递归栈）。最后，DP 和贪心的判别：能证明”局部最优推全局最优”用贪心，否则老老实实写状态转移方程用 DP，01 背包用 DP、部分背包用贪心，这个对比例子记牢就能挡住大半混淆点。

第一章 数据结构与算法：把数据摆明白，把套路用清楚