二叉树

特点：
1. 所有节点最多拥有2个子节点
2. 左子树的键值小于根的键值，右子树的键值大于根的键值

遍历

  1. 前序遍历 根-左-右

    1. def preorder(self,root)
    2.  if root:
    3.      self.traverse_path,append(root,val)
    4.      self.preorder(root, left)
    5.      self.preorder(root,right)

  2. 中序遍历 左-根-右

    1. def inorder(self,root)
    2.  if root:
    3.      self.inorder(root, left)
    4.      self.traverse_path,append(root,val)
    5.      self.inorder(root,right)

  3. 后续遍历 左-右-根

    1. def postorder(self,root)
    2.  if root:
    3.      self.postorder(root, left)
    4.      self.postorder(root,right)
    5.      self.traverse_path,append(root,val)

平衡二叉树

Alv树

基于avl算法，即是avl树
特点：

  1. 满足二叉树的条件
  2. 任何节点的两个子树的高度最大差为1

如果在avl 树，中进行插入和删除节点操作，可能导致avl树失去平衡，那么可以通过旋转重新达到平衡。因此我们说的二叉树也称自平衡二叉树

红黑树

红黑树和avl树类似，都是在进行插入和删除操作时通过特定的操作保持二叉树的平衡，从而获得较高的查找性能。
特点：

  1. 满足二叉树的条件
  2. 红黑树要求从根节点到叶子节点的最长路径不大于最短路径的两倍

    java中，TreeSet和TreeMap的底层就是用的这个方法

  1. 根节点是黑色
  2. 节点是红色或者黑色
  3. 叶子节点(nil，空节点)是黑色
  4. 每个红色节点的两个子节点是黑色

红黑树与AVL树的比较： AVL是严格的平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多； 红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低开销； 所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL树

B Tree

B树是平衡多路查找树（有多个查找路径，不止2个），是一种平衡的多叉树。因为B树是平衡树，每个节点到叶子节点的高度都是相同的，这样可以保证B树的查询是稳定的。
与二叉树相比，B-tree利用多个分支（二叉树只有2个分支）节点，减少了获取记录时所经历的节点数，从而达到节省存取时间的目的。

特点：

  1. 相比平衡二叉树，每个节点的关键字增多了
  2. 所有的叶子节点都在同一层

B+ Tree

B+tree 是在 B- tree基础上的优化，使其更适应存储索引结构。
B- tree的结构中，每个节点不仅包括数据的key值，也包括data值。而每一页的存储空间都是有限的，如果data数据较大的时候，会导致，每一页中存储的key比较少，当存储的数据量比较大时，同样会导致B- tree的查询深度很大，增加磁盘IO次数，进而影响查询效率
B+ tree中，非叶子节点上只存储key的信息，这样可以加大每一页中存储key的数量，降低B+ tree的高度。

特点（与B Tree相比）：

  1. 非叶子节点只存储key信息
  2. 所有叶子节点之间有一个链指针
  3. B+的非叶子节点只进行数据的索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样。
  4. B+树的应用场景主要是数据库索引结构，数据库的查询有时候可能一次多条，如果分布在不同的层（树的层级），那么在取出数据后，还需要做排序。而在一个层级上，且有指针连接各个叶子节点也使得查询效率更高。

Leetcode

BFS（通过队列）

image.png（LeetCode题）

  1. public List<List<Integer>> levelOrder(TreeNode root) {
  2.     List<List<Integer>> listList = new ArrayList<>();
  3.     if (root == null) return  listList;
  5.     Queue<TreeNode> queue = new LinkedList<>();
  6.     queue.add(root);
  8.     while (!queue.isEmpty()) {
  9.         int size = queue.size();
  10.         List<Integer> list = new ArrayList<>();
  11.         for (int i = 0; i < size; i++) {
  12.             TreeNode poll = queue.poll();
  13.             list.add(poll.val);
  15.             if (poll.left != null) {
  16.                 queue.add(poll.left);
  17.             }
  18.             if (poll.right != null) {
  19.                 queue.add(poll.right);
  20.             }
  21.         }
  22.         listList.add(list);
  23.     }
  25.     return listList;
  26. }

DFS（递归）

范式

  1. def recursion(level, param1, param2, ...) :
  2.     #step1: 返回条件
  3.     if level > MAX_LEVEL:
  4.         print_result
  5.         return
  7.     #step2:处理逻辑
  8.     process_data(level, data)
  10.     #step3:继续下沉到下一级
  11.     recursion(level+1, param1, param2, ...)
  13.     #step4:当层处理完的剩余逻辑，如果有的话
  14.     reverse_state(level)