前面我们讲了二叉树，二叉搜索树(BST)就是特殊的二叉树而已。

首先，BST性质：

• 对于BST的每个节点node，左子树节点的值都比node的值小，右子树节点的值都比node的值大。
• 对于BST的每一个节点node，它的左子树和右子树都是BST
• BST的中序遍历是升序。

二叉搜索树并不算难，但是基于BST的数据结构有二叉平衡树(AVL)，红黑树等等，还有B+树，线段树等结构都是基于BST的思想来设计的。

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。基本操作的运行时间为O(lgN)

对于特性三，我们输入一颗BST树，可以通过中序遍历把BST中每个节点的值升序打印出来。

第五章 面向对象编程风格

5.1 面向对象编程概念

面向对象编程概念的两项最主要特质是：继承和多态。前者使我们得以将一群相关的类组织起来，并让我们得以分享其间的共通数据和操作行为，后者让我们在这些类之上进行编程时，可以如同操作单一个体，而非互相独立的类，并赋予我们更多弹性来加入或移除任何特定类。

继承机制定义了父子关系。父类定义了所有子类共通的共有接口和私有实现。每个子类都可以增加或覆盖（override）继承而来的东西，以实现其自身独特的行为。

在C++中，父类被称为基类（base class），子类被称为派生类(derived class)。父类和子类之间的关系则称为继承体系。

抽象基类： 例如下面的LibMat，LibMat用来定义图书馆系统中所有馆藏的共通操作行为，包括check_in(),check_on(),due_data(),find()等等。LibMat并不代表图书馆借阅管理系统中实际存在的任何一个馆藏，仅仅是为了我们设计上的需要而存在。但事实上这个抽象十分关键。我们称之为"抽象基类"。

第三章 HTTP报文内的HTTP信息

HTTP通信过程包括从客户端发往服务器端的请求及从服务器端返回客户端的响应。

Dijkstra思想

前面我们讲图的遍历的时候讲过，图的存储主要就是邻接矩阵和邻接表。

我们知道广度优先搜索(BFS)也可以查找最短路径，但是却只能针对无权图。

最短路径：带权路径长度最短的那条路就是最短路径。

带权有向图的最短路径问题可以分为两类：一是单源最短路径，即求图中某一顶点到其他顶点的最短路径，可以通过经典的Dijkstra（狄杰斯特拉）算法求解；二是求每对顶点间的最短路径，可通过Floyd（佛洛依德）算法求解。

Dijkstra和Floyd还有一个很大的区别就是Dijkstra不能求解权值为负的问题，Floyd可以求解。

第四章 返回结果的HTTP状态码

HTTP状态码负责表示客户端HTTP请求的返回结果，标记服务器端的处理是否正常，通知出现的错误等。

31. 下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3]，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3]的下一个排列是 [1,3,2]。 类似地，arr = [2,3,1]的下一个排列是 [3,1,2]。 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1]不存在一个字典序更大的排列。 给你一个整数数组 nums ，找出 nums的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

386. 字典序排数

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

示例：

输入：n = 13

输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

数组和指针的区别

1. 概念

• 数组：数组是用于存储多个相同类型数据的集合。
• 指针：指针相当于一个变量，但是它和不同变量不一样，它存放的是其它变量在内存中的地址。

1. const 含义

常类型是指使用类型修饰符const说明的类型，常类型的变量或对象的值是不能被更新的。

岛屿系列题⽬的核⼼考点就是⽤ DFS/BFS 算法遍历⼆维数组。

我们可以根据二叉树遍历框架写出DFS框架。

DFS代码框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

void dfs(vector<vector<int> >& grid, int i, int j, vector<bool>& visited){
  int m = grid.size(), n = grid[0].size();
  //base case
  if(i < 0 || j < 0 || i >= m || j >= n) return;
  //已经访问过
  if(visited[i][j]) return;
  //进入节点(i,j)
  visited[i][j] = true;
  dfs(grid, i - 1, j, visited);
  dfs(grid, i + 1, j, visited);
  dfs(grid, i, j - 1, visited);
  dfs(grid, i, j + 1, visited);
}

因为⼆维矩阵本质上是⼀幅「图」，所以遍历的过程中需要⼀个 visited 布尔数组防⽌⾛回头路，如果你理解了之后，那么所有的岛屿问题就迎刃而解了。