二叉树

二叉树

除此之外，关于“树”，还有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。它们的定义是这样的：

“高度”这个概念，其实就是从下往上度量，比如我们要度量第 10 层楼的高度、第 13 层楼的高度，起点都是地面。所以，树这种数据结构的高度也是一样，从最底层开始计数，并且计数的起点是 0。

“深度”这个概念在生活中是从上往下度量的，比如水中鱼的深度，是从水平面开始度量的。所以，树这种数据结构的深度也是类似的，从根结点开始度量，并且计数起点也是 0。

“层数”跟深度的计算类似，不过，计数起点是 1，也就是说根节点位于第 1 层。

高度、深度、层数

完全二叉树的定义: 叶子节点都在最底下两层, 最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大. 满二叉树的定义: 除了叶子节点,每个节点都有左右两个子节点.

存储一棵二叉树，我们有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。

比较简单、直观的链式存储法。

链式

基于数组的顺序存储法:

堆和堆排序 堆是一种完全二叉树,最常用的存储方式就是数组

前序遍历 中序遍历 和 后序遍历

• 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

• 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

• 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

前中后

写递归代码的关键，就是看能不能写出递推公式，而写递推公式的关键就是，如果要解决问题 A，就假设子问题 B、C 已经解决，然后再来看如何利用 B、C 来解决 A。所以，我们可以把前、中、后序遍历的递推公式都写出来

前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

前、中、后序遍历的时间复杂度是 O(n)

红黑树: 平衡二叉查找树

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树，

• 根节点是黑色的；

• 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；

• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；

• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。

红黑树规定, 插入的节点必须是红色的, 而且,二叉查找树中新插入的节点都是放在叶子节点上.

• 如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。

• 如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。

递归树

归并排序递归树是一棵满二叉树

讲到，满二叉树的高度大约是 log2​n，所以，归并排序递归实现的时间复杂度就是 O(nlogn)

快速排序在最好情况下，每次分区都能一分为二，这个时候用递推公式 T(n)=2T(2n​)+n，很容易就能推导出时间复杂度是 O(nlogn)。但是，我们并不可能每次分区都这么幸运，正好一分为二。我们假设平均情况下，每次分区之后，两个分区的大小比例为 1:k。当 k=9 时，如果用递推公式的方法来求解时间复杂度的话，递推公式就写成 T(n)=T(10n​)+T(109n​)+n。

递归

堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。

堆满足的条件：

• 堆是一个完全二叉树；

• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。

堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值

数组堆化

堆化： 从上往下、从下网上

堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换

数组中下标为 i 的节点的左子节点，就是下标为 i∗2 的节点，右子节点就是下标为 i∗2+1 的节点，父节点就是下标为 2i​ 的节点。

删除堆顶元素

堆这种数据结构实现的排序算法，就叫做堆排序。这种排序方法的时间复杂度非常稳定，是 O(nlogn)，并且它还是原地排序算法。

我们可以把堆排序的过程大致分解成两个大的步骤，建堆和排序。

1. 建堆我们首先将数组原地建成一个堆。所谓“原地”就是，不借助另一个数组，就在原数组上操作。建堆的过程，有两种思路。

整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。

堆的应用一： 优先级 赫夫曼编码、图的最短路径、最小生成树算法等等。

堆的应用二：利用堆求 Top K

针对静态数据，如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。

遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，时间复杂度就是 O(nlogK)。

广度搜索（Breadth-First-Search）

即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

深度优先搜索（Depth-First-Search），简称 DFS

在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m。因为我们是在主串中查找模式串，所以 n>m。

学习路线

二叉树的最大和最小深度

var maxDepth = function (root) {
  var max = 0;

  function getDeep(root, max) {
    // 退出条件
    if (root.value == null) return max;
    // 层级加一
    max = max + 1;
    leftValue = root.left || getDeep(root.left, max);
    rightValue = root.right || getDeep(root.right, max);
    return leftValue > rightValue ? leftValue : rightValue;
  }
  getDeep(root, 0);
};

var maxDepth = function (root) {
  if (!root) {
    return 0;
  } else {
    const left = maxDepth(root.left);
    const right = maxDepth(root.right);
    return Math.max(left, right) + 1;
  }
};

// BFS 写法 // 关键是运用好层级 queue 这个队列方式 运用好先进先出

const maxDepth = (root) => {
  if (root == null) return 0;
  const queue = [root];
  let depth = 1;
  while (queue.length) {
    // 当前层的节点个数
    const levelSize = queue.length;
    // 逐个让当前层的节点出列
    for (let i = 0; i < levelSize; i++) {
      // 当前出列的节点
      const cur = queue.shift();
      // 左右子节点入列
      if (cur.left) queue.push(cur.left);
      if (cur.right) queue.push(cur.right);
    }
    // 当前层所有节点已经出列，如果队列不为空，说明有下一层节点，depth+1
    if (queue.length) depth++;
  }
  return depth;
};

二叉树最小深度

var minDepth = function (root) {
  if (!root) return 0;

  if (!root.left) return 1 + minDepth(root.left);
  if (!root.right) return 1 + minDepth(root.right);

  const leftMinDepth = minDepth(root.left);
  const rightMinDepth = minDepth(root.right);

  const result = 1 + Math.min(leftMinDepth, rightMinDepth);

  return result;
};

var minDepth = function (root) {
  if (root == null) return 0;
  else if (root.left == null) {
    return minDepth(root.right) + 1;
  } else if (root.right == null) {
    return minDepth(root.left) + 1;
  } else {
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
  }
};

最小深度