二叉树（Binary-Tree）与经典问题

二叉树的基础知识

  • 链表是特殊的树形结构
  • 基本性质
    • 每个节点的度最多为 2
    • 度为 0 的节点比度为 2 的节点多一个
      • 证明：设度为 0 的结点为 n0，度为 1 的结点为 n1，度为 2 的结点为 n2。
      • 那么总结点数为 n0 + n1 + n2，而总边数为 0 · n0 + 1 · n1 + 2 · n2。
      • 而我们知道总边数等于总结点数减去 1，那么有 n0 + n1 + n2 − 1 = 0 · n0 + 1 · n1 + 2 · n2，即 n0 − 1 = n2。

  • 遍历 | | | | —- | —- | | 前序遍历 | 根左右 | | 中序遍历 | 左根右 | | 后序遍历 | 左右跟 |

  • 特殊的二叉树

二叉树 (Binary-Tree) 与经典问题 - 图1

  • 关于树结构的理解

    • 节点表示集合（set）,边表示关系（relationsgip）

  • 学习二叉树的作用

    • 二叉树是理解高级数据结构的基础。
    • 完全二叉树 – 堆、优先队列
    • 多叉树/森林 – 字典树、AC 自动机、并查集
    • 二叉排序树 (BST, Binary Search Tree) – AVL 树、2-3 树、红黑树、B-树、B+ 树
    • 二叉树是练习递归技巧的最佳选择。
    • 学习二叉树后，可以使用左孩子右兄弟法来节省空间。

二叉树 (Binary-Tree) 与经典问题 - 图2

练习递归技巧的最佳选择

二叉树 (Binary-Tree) 与经典问题 - 图3

二叉树的基本操作(经典面试题)

  • 144. 二叉树的前序遍历
  • 589. N 叉树的前序遍历
  • 平衡⼆叉树
  • 从上到下打印⼆叉树 Ⅱ
  • ⼆叉搜索树的第 k ⼤节点
  • ⼆叉树的锯⻮形层序遍历
  • 完全⼆叉树的节点个数
  • 树的⼦结构
  • 从前序与中序遍历序列构造⼆叉树
  • 路径总和
  • 监控⼆叉树
  • 翻转⼆叉树
  • ⼆叉树的层序遍历 Ⅱ
  • ⼆叉树最⼤宽度