链表与二叉树

链表与二叉树 从数据结构的角度进行分析

链表与二叉树

• 链表
  • 分类
    • 单链表
    • 双链表
    • 单循环链表
    • 双循环链表
      • LinkedList<E>
  • 逻辑
    • 数据域
    • 指针域
    • 操作
      • 删除
        • O(1)(给出被删除结点的引用)
      • 插入
        • O(1)（给出插入位置前面结点的引用）
      • 查找
        • O(n)
  • 存储
    • 无须地址连续
  • 数组
    • 静态链表
  • 头结点
    • 统一操作
  • 题目
    • 复杂链表的复制
      • 单链表+一个 random 指针指向链表中的任意节点或者 null。
    • 多指针
      • 快慢指针
        • 链表倒数第k个节点
        • 两个链表的第一个节点
      • 给点节点值，删除链表中的节点
      • 合并两个排序链表
      • 两数相加
    • 反转链表（反转之前需要保存被更新的原始数据）
• 二叉树（查找O(logn)）
  • B树
  • 逻辑结构
    • 数据域
    • 左子针
    • 右子针
  • 存储结构
    • 三叉链表（多指向双亲结点的指针）
      • 遍历无须递归，循环
    • 二叉链表
    • 一维数组
  • 分类
    • 红黑树
      • TreeMap<K, V>
    • AVL树（二叉平衡搜索树）
      • 平衡二叉树
      • 二叉排序树
  • 题目（遍历相关）
    • 判断是否平衡
    • 查找最近公共祖先
    • 是否镜像
      • 树的子结构
    • 高度/深度/层次
    • 查找路径（数之和）
    • 二叉树转双向链表
    • 二叉搜索树的第k大节点
    • 从上到下打印二叉树
    • 重建二叉树
      • 已知：中序遍历序列，先序/后序
    • 二叉搜索树的后序遍历顺序