数据结构与算法
这是笔记的起点，782 页手写笔记从这里开始。
二叉树
二叉树遍历
前序遍历：根 → 左 → 右 中序遍历：左 → 根 → 右 后序遍历：左 → 右 → 根 层序遍历：从根节点开始从上到下、从左到右
叶子节点：没有子节点的节点 前序：第一次经过就打印 中序：第二次经过才打印 后序：第三次经过才打印 前序和后序无法判断唯一的一棵二叉树，中序可以
二叉树性质
如果一棵树有 n 个节点，则有 n-1 条边 第 i 层最多有 2^(i-1) 个节点 深度为 k 的二叉树最多有 2^k - 1 个节点
二叉树顺序存储
按层序遍历的顺序存储在数组中 左子节点：2i+1，右子节点：2i+2 父节点：(i-1)/2
链表
单向链表
数据结构：通过节点封装数据 每个节点包含数据和指向下一个节点的指针 不能从任意节点直接访问其他节点
双向链表
可以以任意节点为起点直接遍历所有节点（通过指针） 每个节点有前驱指针和后继指针
循环链表
尾节点指向头节点，形成环
链表常见操作
求链表长度、找中间节点（快慢指针法） 递归操作链表 在指定位置插入/删除节点
栈
栈的特性
仅允许在一端进行插入和删除的线性表 先进后出 (LIFO)：First In Last Out 不允许遍历，仅支持 peek 查看栈顶元素
栈的实现
基于数组：固定容量，top 指针 基于链表：动态容量，push/pop 在头部操作 基于链表实现 pop 时需要创建临时变量保存要删除的节点
队列
队列的特性
先进先出 (FIFO)：First In First Out 入队操作：队尾添加元素 出队操作：队头移除元素
队列的 API
add / element：抛出异常 offer / peek：返回特殊值 优先级队列 (PriorityQueue)
排序算法
选择排序 (Selection Sort)
每次从未排序部分选出最小值放到已排序部分末尾 时间复杂度：O(n²) 空间复杂度：O(1) 稳定性：不稳定
冒泡排序 (Bubble Sort)
相邻元素两两比较，每轮把最大的元素"冒泡"到末尾 时间复杂度：O(n²) 空间复杂度：O(1) 稳定性：稳定
插入排序 (Insertion Sort)
将未排序元素插入到已排序部分的正确位置 时间复杂度：O(n²)，对近乎有序的数组接近 O(n) 空间复杂度：O(1) 稳定性：稳定
快速排序 (Quick Sort)
选基准元素，分区后递归排序 时间复杂度：平均 O(n log n)，最坏 O(n²) 空间复杂度：O(log n) 稳定性：不稳定
归并排序 (Merge Sort)
分治法：先递归拆分，再合并两个有序数组 时间复杂度：O(n log n) 空间复杂度：O(n) 稳定性：稳定
堆排序 (Heap Sort)
构建最大堆，每次取出堆顶（最大值） 时间复杂度：O(n log n) 空间复杂度：O(1) 稳定性：不稳定