Shaoqun Liu's blog
搜索文档…
Shaoqun Liu's blog
作者简介
做过的和正在做的项目
我的博物馆
文集
机器学习
图像检索
C/C++学习笔记
Java学习笔记
Python学习笔记
计算机基础学科
算法
数据结构概念小结
链表
栈和队列
树
图
排序算法总结
查找
操作系统
计算机网络
网站运维日记
常用的工具及数据库
英文技术文献翻译
随笔
我的朋友们
推荐阅读
由 GitBook 提供支持
树

0x00 二叉树

二叉树（Binary tree）是一个以树型存储的数据结构，每个结点除数据域外都有一个左孩子（left child）以及一个右孩子（right child）。
满二叉树（perfect binary tree），除最后一层无任何子节点外，每一层上的所有节点都有两个子结点二叉树。另有定义：一棵高度为
hh
 ，并且含有
2h−12^h-1
 个节点的二叉树称为满二叉树。此定义与上述定义等价。
完全二叉树（complete binary tree），对于深度为K的有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
我有必要跟你说一下perfect binary tree和full binary tree的区别，如果按照英文字面来理解的话，full binary tree翻译过来应该是满二叉树，其实不然，这样的字面翻译也是错误的，我们需要依据其具体的定义来理解，国外教材是这样定义full binary tree的：
A full binary tree (sometimes referred to as a proper or plane binary tree) is a tree in which every node has either 0 or 2 children.
从上述国外教材的原话中我们可以知道只要满足所有节点不是有0个就是有2个子节点的树就可以称为full binary tree，如下图：
​
​
上面这个树在我们国内教材的定义上，不是满二叉树，但其确实对应了国外教材中所述的full binary tree的定义，你可以看到我在满二叉树的定义处指出国内教材中的满二叉树应对应国外教材中的perfect binary tree，来让我们看一下国外教材是怎么定义perfect binary tree的：
A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.
下图即为一个满二叉树，即为perfect binary tree：
​
​
此处我们要注意了如果一个二叉树是perfect binary tree那他一定是full binary tree，反之不成立。
在部分国外教材中文译本上，perfect binary tree被翻译为完美二叉树，full binary被翻译为完满二叉树。
下文中所有的满二叉树均指国内教材中有关满二叉树的定义，也就是perfect binary tree。
二叉树常用公式：
  1. 1.
    非空二叉树第
    ii
     层上最多有
    2i−12^{i-1}
     个结点
  2. 2.
    高度为
    hh
     的二叉树至多有
    2h−12^h-1
     个结点
  3. 3.
    第
    ii
     个结点所在的层次（深度）为
    ⌊log⁡2i⌋+1\lfloor\log_2{i}\rfloor+1
  4. 4.
    具有
    NN
     个结点的完全二叉树的高度为
    ⌈log⁡2(N+1)⌉\lceil\log_2{(N+1)}\rceil
  5. 5.
    对于任意二叉树，度为0的结点记为
    N0N_0
     ，度为2的结点记为
    N2N_2
     ，则必有
    N0=N2+1N_0=N_2+1
     ，即度为0的结点总比度为2的结点多一个
  6. 6.
    一棵具有
    NN
     个结点的树，所有结点的度数之和为
    N−1N-1
  7. 7.
    度为n的结点，第i层最多有
    ni−1n^{i-1}
     个结点
注：
​
⌊x⌋\lfloor x\rfloor
 为向下取整符号，结果为不大于x的最大整数，例如
⌊2.9⌋=2\lfloor2.9\rfloor=2
​
⌈x⌉\lceil x\rceil
 为向上取整符号，结果为不小于x的最小整数，例如
⌈2.1⌉=3\lceil2.1\rceil=3
树中一个结点的子结点的个数称为结点的度（degree of node），度大于0的结点称为分支结点（branch node），度等于0的结点称为叶子结点（leaf node）或终端结点（terminal node）。树中结点最大的度数称为树的度。
树的路径长度是从树的根节点到每一个结点的路径长度的总和。

0x01 二叉树的遍历

先看一棵树：

0x00 先序遍历

先序遍历（Preorder Traversal）的遍历过程为先访问根节点，然后递归先序遍历左子树，后递归先序遍历右子树，则对上面的那个树遍历序列应为：
1
ABDCEGFHI
Copied!
我们可以通过LeetCode题目，144. Binary Tree Preorder Traversal来练习树的先序遍历过程，在此题中，不需要你手动建树，他会给你建好一个树然后作为函数的输入参数给你，你只需完成先序遍历的过程，然后输出这个序列即可，给出我写的一个基于递归算法的树的先序遍历的代码：
1
class Solution {
2
public:
3
std::vector<int> preorderTraversal(TreeNode* root) {
4
std::vector<int> ret;
5
if (root)
6
{
7
ret.emplace_back(root->val);
8
std::vector<int> left = preorderTraversal(root->left);
9
ret.insert(ret.end(), left.begin(), left.end());
10
std::vector<int> right = preorderTraversal(root->right);
11
ret.insert(ret.end(), right.begin(), right.end());
12
}
13
return ret;
14
}
15
};
Copied!

0x01 中序遍历

中序遍历（Inorder Traversal）先依次中序遍历左子树，然后访问根节点，最后依次中序遍历右子树，则对上面的那个树中序遍历序列应为：
1
BDAGECHFI
Copied!
同样通过LeetCode题目94. Binary Tree Inorder Traversal来练习树的中序遍历，基于递归算法的代码如下：
1
class Solution {
2
public:
3
std::vector<int> inorderTraversal(TreeNode* root) {
4
std::vector<int> ret;
5
if (root)
6
{
7
std::vector<int> left = inorderTraversal(root->left);
8
ret.insert(ret.end(), left.begin(), left.end());
9
ret.emplace_back(root->val);
10
std::vector<int> right = inorderTraversal(root->right);
11
ret.insert(ret.end(), right.begin(), right.end());
12
}
13
return ret;
14
}
15
};
Copied!

0x02 后序遍历

后序遍历（Postorder Traversal）的遍历顺序为先后序遍历左子树，然后后序遍历右子树，最后后序遍历根节点。则对于上面的那个树后序遍历序列应为：
1
DBGEHIFCA
Copied!
同样通过LeetCode题目145. Binary Tree Postorder Traversal来训练后序遍历的代码，使用递归算法的代码如下：
1
class Solution {
2
public:
3
std::vector<int> postorderTraversal(TreeNode* root) {
4
std::vector<int> ret;
5
if (root)
6
{
7
std::vector<int> left = postorderTraversal(root->left);
8
ret.insert(ret.end(), left.begin(), left.end());
9
std::vector<int> right =
10
postorderTraversal(root->right);
11
ret.insert(ret.end(), right.begin(), right.end());
12
ret.emplace_back(root->val);
13
}
14
return ret;
15
}
16
};
Copied!
不知道细心的你有没有发现，在树的前序遍历、中序遍历以及后序遍历我们所写出来的代码中，不一样的地方只有那个if块里面语句的顺序调换了一下而已。
下面给出一个非递归版的后序遍历实现：
1
class Solution {
2
public:
3
std::vector<int> postorderTraversal(TreeNode* root) {
4
std::vector<int> ret;
5
if (root)
6
{
7
std::stack<TreeNode*> stk;
8
stk.push(root);
9
while (!stk.empty())
10
{
11
TreeNode *dummy = stk.top();
12
stk.pop();
13
if (dummy->left)
14
{
15
stk.push(dummy->left);
16
}
17
if (dummy->right)
18
{
19
stk.push(dummy->right);
20
}
21
ret.emplace_back(dummy->val);
22
}
23
std::reverse(ret.begin(), ret.end());
24
}
25
return ret;
26
}
27
};
Copied!
非递归后序遍历到某个结点时，栈中的序列即为从根节点到此结点的路径

0x03 层序遍历

层序遍历（Level Order Traversal）和上面三种就不一样了，层序遍历基本上就是我们人类肉眼的遍历方法，对于上面图中的那个二叉树，层序遍历顺序为：
1
ABCDEFGHI
Copied!
通过LeetCode题目102. Binary Tree Level Order Traversal来练习层序遍历的过程，注意此题要求你返回一个vector<vector<int>>，输入二叉树的每一层都要单独放在一个vector里面，然后把所有层的vector都打包在一个vector里面返回，使用递归算法实现的代码如下：
1
class Solution {
2
​
3
void levelOrder(std::vector<std::vector<int>> &res, std::vector<TreeNode*> current)
4
{
5
std::vector<int> nums;
6
std::vector<TreeNode*> next;
7
for (TreeNode* node : current)
8
{
9
if (node)
10
{
11
nums.emplace_back(node->val);
12
next.emplace_back(node->left);
13
next.emplace_back(node->right);
14
}
15
}
16
if (nums.size())
17
{
18
res.emplace_back(nums);
19
}
20
if (next.size())
21
{
22
levelOrder(res, next);
23
}
24
}
25
public:
26
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
27
std::vector<TreeNode*> current;
28
current.emplace_back(root);
29
std::vector<std::vector<int>> res;
30
levelOrder(res, current);
31
return res;
32
}
33
};
Copied!
这份代码运行时间4ms击败98.92%的人，但此代码使用了递归算法，基本思路为，我每走到一层记录当前这层所有节点的子节点指针（即为下一层节点指针）放在一个vector里面，然后将其作为参数递归传下去，然后下一次递归的时候即遍历传入的当前一层的指针列表依次记录其中元素的值，然后插入结果集的vector即可。

0x02 二叉树的建立

0x00 什么样的遍历顺序组合可以独一地确立一颗二叉树

二叉树有四种遍历方式，先序遍历、中序遍历、后序遍历以及层序遍历，先给定这四种遍历方式中的任意两个，通过这两个遍历顺序可以唯一的确定一颗二叉树吗？
答案是：当给定中序遍历序列以及剩下的三种任意一个的话，即可唯一地确立一颗二叉树。
如果不给定中序遍历序列，而是给定剩下三种遍历序列的组合的话，是不能唯一地确立二叉树的，看如下示例：
现有二叉树：
1
1
2
/
3
2
Copied!
给定先序遍历序列为12，以及后序遍历序列为21，我们可以看出如下两树均可满足相同的先序及后序遍历序列，所以其不能唯一地确定二叉树：
1
1 | 1
2
/ | \
3
2 | 2
4
树1 | 树2
Copied!
但如果给定先序遍历序列为12和中序遍历序列21，就能唯一地确定所要求得的二叉树为树1，因为树2的中序遍历序列为12，就能把结点2牢牢地限制住其为1的左孩子。
如果想求得唯一的二叉树，必需有中序遍历序列以及剩下三种遍历序列中的任意一个，如果没有中序遍历序列，剩下的三种遍历序列无论怎么组合，即便三个全部给出也依然无法求得唯一的二叉树。
现在考虑一个问题，假设说我只知道前序或后序遍历序列，则符合此遍历序列的二叉树一共有多少呢？由此可延伸一个相同的问题，N个结点可以构成多少种不同的二叉树，此题答案依然为卡特兰数公式：
1N+1C2NN\frac{1}{N+1}C_{2N}^{N}

0x01 通过先序遍历和中序遍历建立二叉树

通过LeetCode题目来练习使用先序遍历和中序遍历建立二叉树的过程，题目链接105. Construct Binary Tree from Preorder and Inorder Traversal，下面的代码使用递归算法完成，效率自然不高：
1
class Solution {
2
​
3
TreeNode * buildTree(std::vector<int>& preorder, int ps, std::vector<int>& inorder, int is, int ie)
4
{
5
if (ps >= preorder.size() || is >= ie)
6
{
7
return nullptr;
8
}
9
TreeNode *root = new TreeNode(preorder[ps]);
10
int i = is;
11
for (; i < ie; ++i)
12
{
13
if (inorder[i] == preorder[ps])
14
{
15
break;
16
}
17
}
18
root->left = buildTree(preorder, ps + 1, inorder, is, i);
19
root->right = buildTree(preorder, ps + i - is + 1, inorder, i + 1, ie);
20
return root;
21
}
22
public:
23
TreeNode * buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
24
return buildTree(preorder, 0, inorder, 0, inorder.size());
25
}
26
};
Copied!
大致说一下基本的算法思路，对于上面图中的那个二叉树，其先序遍历序列为：
1
ABDCEGFHI
Copied!
中序遍历序列为：
1
BDAGECHFI
Copied!
先序遍历首先访问的为根节点，由先序遍历的序列可知第一个根节点为A，然后我们在中序遍历里面查找A，因题目已经给出条件You may assume that duplicates do not exist in the tree.说明树中没有重复元素了，所以我们可以直接在中序遍历的序列里查找根节点A所在的位置，依中序遍历规则可知，A前面的元素BD即为A作为根节点时的左孩子，A后面的元素GECHFI即为A作为根节点时的右孩子，然后再向下递归得到以结点B为根节点的子树，依次递归直至先序遍历序列完成一遍时算法结束。
上面的算法，我们每次递归时都会有一个for循环来查找当前根节点在中序遍历序列中的位置，我们可以使用unordered_map将其消除，用空间换时间，在递归之前，我们提前遍历中序遍历序列，将中序遍历的数值作为key和其在vector内的下标作为value，使用unordered_map将其一一对应起来，这样我们可以直接使用二叉树遍历的数值（作为unordered_map的key）来快速找到其在中序遍历序列中的下标（作为unordered_map的value），从而省去了每一次进入使用for循环查找的过程，大大提升了算法的效率，代码如下：
1
class Solution {
2
​
3
std::unordered_map<int, int> iMap;
4
​
5
TreeNode * buildTree(std::vector<int>& preorder, int ps, std::vector<int>& inorder, int is, int ie)
6
{
7
if (ps >= preorder.size() || is >= ie)
8
{
9
return nullptr;
10
}
11
TreeNode *root = new TreeNode(preorder[ps]);
12
int i = iMap[preorder[ps]];
13
root->left = buildTree(preorder, ps + 1, inorder, is, i);
14
root->right = buildTree(preorder, ps + i - is + 1, inorder, i + 1, ie);
15
return root;
16
}
17
public:
18
TreeNode * buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
19
for (int i = 0; i < inorder.size(); ++i)
20
{
21
iMap[inorder[i]] = i;
22
}
23
return buildTree(preorder, 0, inorder, 0, inorder.size());
24
}
25
};
Copied!
进行上述优化后，代码的运行时间从20ms缩减到了8ms可见效果还是十分明显的。

0x02 通过中序遍历和后序遍历建立二叉树

通过中序遍历序列和后序遍历序列可以确立一棵唯一的二叉树，我们可以通过LeetCode题目106. Construct Binary Tree from Inorder and Postorder Traversal来练习，基于递归算法的代码如下：
1
class Solution {
2
​
3
std::unordered_map<int, int> iMap;
4
​
5
TreeNode * buildTree(std::vector<int>& inorder, int is, int ie, std::vector<int>& postorder, int ps, int pe)
6
{
7
if (is >= ie || ps >= pe)
8
{
9
return nullptr;
10
}
11
TreeNode *root = new TreeNode(postorder[pe - 1]);
12
int lsize = iMap[postorder[pe - 1]] - is;
13
root->left = buildTree(inorder, is, is + lsize, postorder, ps, ps + lsize);
14
root->right = buildTree(inorder, iMap[postorder[pe - 1]] + 1, ie, postorder, ps + lsize, pe - 1);
15
return root;
16
}
17
public:
18
TreeNode * buildTree(std::vector<int>& inorder, std::vector<int>& postorder) {
19
for (int i = 0; i < inorder.size(); ++i)
20
{
21
iMap[inorder[i]] = i;
22
}
23
return buildTree(inorder, 0, inorder.size(), postorder, 0, postorder.size());
24
}
25
};
Copied!

0x03 线索二叉树

0x00 基本概念

在传统的二叉树的实现中，在一棵树中往往由很多空指针，比如在叶子结点中以及在那些缺少某个孩子的结点中，线索二叉树（Threaded Binary Tree）的实质就是为了把这些空指针全部利用起来，利用这些空的指针域来存放其直接前驱或后继的指针，加快查找结点前驱和后继的速度。线索化的实质就是设法利用二叉树中多余的空指针将二叉树变为一个双向链表。
二叉树为一种逻辑结构，线索二叉树是加上线索后的链表结构，也就是说，它是二叉树在计算机内部的一种存储结构，所以线索二叉树是一种物理结构。
线索二叉树的存储结构：
1
struct TreeNode {
2
int val; // 数据域
3
TreeNode *left; // 左孩子
4
TreeNode *right; // 右孩子
5
int ltag; // 左标识域
6
int rtag; // 右标识域
7
}
Copied!
其标识域含义如下：
  • ltag
    • 0：left指针指向结点的左孩子
    • 1：left指针指向结点的前驱
  • rtag
    • 0：right指针指向结点的右孩子
    • 1：right指针指向结点的后继
这里的前驱和后继是相对于构建线索二叉树的遍历序列而言的。
N个结点的线索二叉树含有N+1个线索。
在先序线索树、中序线索树和后序线索树三者之中，后序线索树的遍历仍然需要栈的支持，后序线索树在进行遍历时，最后访问根节点，如果从右孩子x返回访问父节点，则此节点的右孩子不一定为空（右指针无法指向其后序遍历的后继），因此后序线索树可能通过指针无法遍历整个二叉树，则需要栈的支持。而先序和中序线索树则不必。由此可延伸一个问题即为，使用后序遍历线索化后的二叉树仍不能有效求解后序后继节点。

0x01 建立中序线索二叉树

如下为基于递归算法的中序线索二叉树的建立，函数的参数为需要线索化的二叉树的根节点，代码如下：
1
struct TreeNode {
2
int val;
3
bool ltag; // false: left child, true: previous
4
bool rtag; // false: right child, true: succeed
5
TreeNode *left;
6
TreeNode *right;
7
TreeNode(int x) : val(x), ltag(false), rtag(false), left(nullptr), right(nullptr) {}
8
};
9
​
10
class Solution {
11
​
12
void inThreading(TreeNode *root, TreeNode *&pre)
13
{
14
if (root)
15
{
16
inThreading(root->left, pre); // 线索化左子树
17
if (!root->left)
18
{
19
root->left = pre;
20
root->ltag = true;
21
}
22
if (pre && !pre->right)
23
{
24
pre->right = root;
25
pre->rtag = true;
26
}
27
pre = root;
28
inThreading(root->right, pre); // 线索化右子树
29
}
30
}
31
public:
32
TreeNode * convertToThreadedTreeWithInorderTraversal(TreeNode *root)
33
{
34
TreeNode *pre = nullptr;
35
inThreading(root, pre);
36
return root;
37
}
38
};
Copied!

0x02 建立后序线索二叉树

如下为建立后序线索二叉树的代码，仅变动了中序线索二叉树代码的递归顺序：
1
// 二叉树结点的存储结构参考建立中序线索二叉树的代码
2
​
3
class Solution {
4
​
5
void inThreading(TreeNode *root, TreeNode *&pre)
6
{
7
if (root)
8
{
9
inThreading(root->left, pre);
10
inThreading(root->right, pre);
11
if (!root->left)
12
{
13
root->left = pre;
14
root->ltag = true;
15
}
16
if (pre && !pre->right)
17
{
18
pre->right = root;
19
pre->rtag = true;
20
}
21
pre = root;
22
}
23
}
24
public:
25
TreeNode * convertToThreadedTreeWithPostorderTraversal(TreeNode *root)
26
{
27
TreeNode *pre = nullptr;
28
inThreading(root, pre);
29
return root;
30
}
31
};
Copied!

0x04 树、森林与二叉树之间的相互转换

0x00 树转化为二叉树

  1. 1.
    树中所有带有相同双亲的兄弟结点之间加一条连线
  2. 2.
    对树中不是双亲结点的第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该节点与双亲结点之间的连线
看上图是要注意的一点就是：E和F，在变化之后，F由原来E的兄弟结点变为E的右孩子。

0x01 二叉树转化为树

  1. 1.
    若某结点是其双亲结点的左孩子，则把该结点的右孩子，右孩子的右孩子等等等等都与这些结点的双亲结点连起来
  2. 2.
    删除原二叉树中所有双亲结点与右孩子结点的连线

0x02 二叉树转化为森林

如果一颗二叉树有右孩子，那么他可以转换为森林，否则，其只能转化为一棵树。
  1. 1.
    从根节点开始，若右孩子存在，则把与右孩子结点的连线删除
  2. 2.
    再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除
  3. 3.
    循环往复直到所有这些根节点与右孩子的连线都删除为止
  4. 4.
    然后将分离的二叉树全部转化为树
对于根节点来说，去除其右孩子的连线之后，左边的左子树部分就不动了，往下递归也是这个过程只操心右孩子，不再操心其左孩子
高度为h的满二叉树转换为森林后所含树的个数一定为h。此处要注意二叉树转换成的树或森林是唯一的。

0x03 森林转化为二叉树

  1. 1.
    将森林中的每棵树变为二叉树
  2. 2.
    因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树
一定是按给定的从左到右的顺序连接

0x05 二叉排序树（又名二叉搜索树或二叉查找树）

二叉排序树，又名二叉搜索树或二叉查找树，在英文里一般将其称为Binary Search Tree，简写为BST，二叉排序树要么为空树，要么具有如下的三大基本特征：
  • 若左子树非空，则左子树上所有结点的关键字值均小于根节点的关键字值
  • 若右子树非空，则右子树上所有结点的关键字值均大于根节点的关键字值
  • 左右子树本身分别也是一颗二叉排序树
因为总有左子树的值<根节点的值<右子树的值，所以对其进行中序遍历总能得到一个递增的有序序列。
二叉排序树理想情况下的高度为：
⌈log⁡2(n+1)⌉\lceil \log_2{(n+1)}\rceil

0x00 二叉排序树的插入

从一道LeetCode题目说起，701. Insert into a Binary Search Tree，此题目要求我们在一颗即成二叉排序树内插入一个元素，使用递归算法，我们可以清晰地得到整个的流程，如下：
1
class Solution {
2
​
3
public:
4
TreeNode * insertIntoBST(TreeNode* root, int val) {
5
if (!root)
6
{
7
return new TreeNode(val);
8
}
9
if (root->val < val)
10
{
11
root->right = insertIntoBST(root->right, val);
12
}
13
else if (root->val > val)
14
{
15
root->left = insertIntoBST(root->left, val);
16
}
17
return root;
18
}
19
};
Copied!
由此可见，新插入的结点一定是叶子结点，如果树中存在相同的元素，那么就将其忽略，如果新插入的元素大于当前结点的值就将其插入到当前结点的右子树中，如果小于就将其插入当前结点的左子树中，递归往复。
递归虽然可以将算法的流程直观地体现出来，但是递归的效率终究不高，上述代码运行时间60ms仅超过了48.11%的人，我们设法将递归消除掉，我一开始惯性思维下写了一个带栈的消除递归的方法，代码如下：
1
class Solution {
2
​
3
public:
4
TreeNode * insertIntoBST(TreeNode* root, int val) {
5
std::stack<TreeNode*> stk;
6
TreeNode **target{ &root };
7
TreeNode *dummy{ root };
8
while (dummy)
9
{
10
if (dummy->val < val)
11
{
12
stk.push(dummy->right);
13
target = &dummy->right;
14
}
15
else if (dummy->val > val)
16
{
17
stk.push(dummy->left);
18
target = &dummy->left;
19
}
20
else
21
{
22
return root;
23
}
24
dummy = stk.top();
25
stk.pop();
26
}
27
*target = new TreeNode(val);
28
return root;
29
}
30
};
Copied!
上面的代码运行时间为44ms，击败了98.93%的人，消除递归确实有效地提升了程序的运行效率，后来我发现那个栈最大长度为1，既然这样我们就可以将那个栈消除掉，代码如下：
1
class Solution {
2
​
3
public:
4
TreeNode * insertIntoBST(TreeNode* root, int val) {
5
TreeNode *next;
6
TreeNode **target{ &root };
7
TreeNode *dummy{ root };
8
while (dummy)
9
{
10
if (dummy->val < val)
11
{
12
next = dummy->right;
13
target = &dummy->right;
14
}
15
else if (dummy->val > val)
16
{
17
next = dummy->left;
18
target = &dummy->left;
19
}
20
else
21
{
22
return root;
23
}
24
dummy = next;
25
}
26
*target = new TreeNode(val);
27
return root;
28
}
29
};
Copied!
上述的代码运行效率应该和用栈的那个代码差不多才对啊，但是上述代码提交上去之后，运行时间居然为80ms，比递归算法的效率还要差，感觉是其编译器优化出现了问题。

0x01 二叉排序树的删除

二叉排序树删除某个结点时，必须先把被删除结点从存储二叉树的链表中摘下，然后将其左子树和右子树与断开的二叉链表重新连接，并且要保持二叉树的性质不会丢失，可以分三种情况去讨论：
  • 如果被删除的结点为叶子结点，那将其直接删除，并不会破坏二叉树的性质
  • 如果被删除的结点仅有左子树或者右子树，则让其子树直接代替被删除的结点
  • 如果被删除的结点同时存在左子树和右子树，用被删除节点的直接前驱或者直接后继来替换当前节点，调整直接前驱或者直接后继的位置，如图：
    ​
    ​
    在上图中，我们要删除47结点，这个结点既有左孩子又有右孩子，我们首先看其中序遍历的序列：
    1
    29, 35, 36, 37, 47, 48, 49, 50, 51, 56, 58, 62, 73, 88, 93, 99
    Copied!
    要删除的结点47的直接前驱为37，所以我们把37拿上去换掉被删除的47，这样就转换成了第一或第二种状况，然后再依第一第二种状况处理即可。
通过LeetCode题目450. Delete Node in a BST来练习上述过程，如果一个结点既有左孩子又有右孩子，此题接受使用其直接前驱或后序两种序列，如下：
1
root = [5,3,6,2,4,null,7]
2
key = 3
3
​
4
5
5
/ \
6
3 6
7
/ \ \
8
2 4 7
9
​
10
Given key to delete is 3. So we find the node with value 3 and delete it.
11
​
12
One valid answer is [5,4,6,2,null,null,7], shown in the following BST. // 使用其直接后继取代被删除的结点
13
​
14
5
15
/ \
16
4 6
17
/ \
18
2 7
19
​
20
Another valid answer is [5,2,6,null,4,null,7].
21
// 使用其直接前驱取代被删除的结点
22
​
23
5
24
/ \
25
2 6
26
\ \
27
4 7
28
// 两种答案均可
Copied!
基于递归算法的代码如下：
1
class Solution {
2
​
3
public:
4
TreeNode * deleteNode(TreeNode* root, int key) {
5
if (!root)
6
{
7
return nullptr;
8
}
9
if (root->val > key)
10
{
11
root->left = deleteNode(root->left, key);
12
}
13
else if (root->val < key)
14
{
15
root->right = deleteNode(root->right, key);
16
}
17
else
18
{
19
if (root->left && root->right)
20
{
21
TreeNode *next = root->right;
22
while (next->left)
23
{
24
next = next->left;
25
}
26
std::swap(root->val, next->val);
27
root->right = deleteNode(root->right, key);
28
}
29
else if (root->left || root->right)
30
{
31
TreeNode *ret =
32
root->left ? root->left : root->right;
33
delete root;
34
return ret;
35
}
36
else
37
{
38
delete root;
39
return nullptr;
40
}
41
}
42
return root;
43
}
44
};
Copied!
此代码运行时间16ms，超过100%的人，在删除时将其分为了三种情况，如果：
  • 其同时具有左右孩子，那寻找其中序遍历的直接后继，然后交换当前结点与其直接后继的值，将其进一步转换为下面的两种情况，继续递归
  • 其仅具有一个孩子，那就用其仅具有的这个孩子来代替这个结点即可
  • 其为叶子结点，直接将其删除，不对二叉排序树的性质产生任何的影响

0x02 二叉排序树的查找

我们先看一道LeetCode题目，700. Search in a Binary Search Tree，此题为简单题，先将其AC掉，然后我们再来分析效率，代码如下：
1
class Solution {
2
public:
3
TreeNode * searchBST(TreeNode* root, int val) {
4
if (root == nullptr)
5
{
6
return nullptr;
7
}
8
if (root->val > val)
9
{
10
return searchBST(root->left, val);
11
}
12
else if (root->val < val)
13
{
14
return searchBST(root->right, val);
15
}
16
return root;
17
}
18
};
Copied!
对于高度为H的二叉排序树，其插入和删除操作的运行时间都是
O(H)O(H)
 ，但在其最坏情况下，当输入序列为一个有序序列时，构造二叉排序树会使得形成的树为一个倾斜的单支树，此时二叉排序树的性能显著变坏，树的高度也增大为输入元素的个数N，由此可见，二叉排序树的查找效率取决于树的深度，树的深度越低查找效率越快。如果一棵二叉排序树的形状为仅有左（右）孩子的单支树，其查找的效率和单链表查找的效率就基本一样了。
整体看来，二叉排序树的查找过程和二分查找差不多，而且两者的平均 性能也不相上下，但是二分查找时其判定树是唯一的，二叉排序树则不一定唯一。但是相比较于二分查找有序数组的情况，当插入或删除一个数据时，有序数组的复杂度为
O(N)O(N)
 ，而二叉排序树则无需移动结点，只需移动指针即可完成插入和删除操作，平均的执行时间为
O(log⁡2(N))O(\log_2(N))
 ，所以在我们选择存储结构时，若当有序表为静态查找表（不会对齐进行频繁的插入删除操作的有序表）时，则适宜使用顺序表作为其存储结构，若有序表时动态查找表，则应选择二叉排序树作为其逻辑结构。

0x03 二叉排序树的判定

如何使用程序来判定一棵给定的树是否为二叉排序树，通过LeetCode题目98. Validate Binary Search Tree来练习，代码如下：
1
class Solution {
2
​
3
void inorder(TreeNode *root, std::vector<int>& result)
4
{
5
if (!root)
6
{
7
return;
8
}
9
inorder(root->left, result);
10
result.push_back(root->val);
11
inorder(root->right, result);
12
}
13
public:
14
bool isValidBST(TreeNode* root) {
15
if (!root)
16
{
17
return true;
18
}
19
std::vector<int> dummy;
20
inorder(root, dummy);
21
for (int i = 1; i < dummy.size(); ++i)
22
{
23
if (dummy[i - 1] >= dummy[i])
24
{
25
return false;
26
}
27
}
28
return true;
29
}
30
};
Copied!
上述代码的空间复杂度为
O(N)O(N)
，占用了额外的空间，我的基本想法是首先求得此二叉树的中序遍历序列，因二叉排序树的中序遍历序列一定是有序的，所以我们可以通过检验此树的中序遍历序列是否有序来判定其是否为二叉排序树。同时编制代码时要注意一点就是，二叉排序树中所有的元素都是独一的，没有重复的。也就是说当输入的二叉树为如下情况时其不为一棵二叉排序树：
1
1
2
/
3
1
Copied!
所以在中序序列判断有序的过程中，还要判断相邻的两个元素是否相同。
下面给出一种空间复杂度为
O(1)O(1)
的解决方案：
1
class Solution {
2
​
3
bool isValidBST(TreeNode* root, long min, long max)
4
{
5
if (!root)
6
{
7
return true;
8
}
9
if (root->val <= min || root->val >= max)
10
{
11
return false;
12
}
13
return isValidBST(root->left, min, root->val) &&
14
isValidBST(root->right, root->val, max);
15
}
16
public:
17
bool isValidBST(TreeNode* root) {
18
if (!root)
19
{
20
return true;
21
}
22
return isValidBST(root, LONG_MIN, LONG_MAX);
23
}
24
};
Copied!
这个题的测试用例完美地替我们想到了当输入数据含有INT_MAX的情况，所以我们在设定初始的min和max时要取LONG_MIN和LONG_MAX。

0x06 平衡二叉树

0x00 基本概念

上一节刚刚说过二叉排序树的性能取决于树的高度，树越高，二叉排序树的性能越差，为了避免树的高度增长地过快，降低二叉排序树的性能，而我们要保证树的任意结点的左右子树高度差的绝对值（平衡因子）不超过1，这样的树称为平衡二叉树（Self-balancing binary search tree或Balanced binary tree或AVL）。
注：AVL是最早实现的一种自平衡二叉搜索树，AVL的全称为Adelson-Velskii and Landis，这是以AVL树的三个创始人的名字首字母命名的，就像RSA算法一样。但有些国内的教材上会将平衡二叉树和AVL树放在一起谈，甚至说平衡二叉树就是AVL树，这样的说法是不严谨的，严格来说，AVL树是平衡二叉树的一种。
平衡二叉树要么是空树，要么满足如下的2个特征：
  • 其左子树和右子树均为平衡二叉树
  • 左子树和右子树高度差的绝对值不超过1
平衡二叉树第h层最少结点数的递推公式：
Nh=Nh−1+Nh−2+1N_h=N_{h-1}+N_{h-2}+1
 ，其中
N1=1,N2=2N_1=1,N_2=2
 。

0x01 平衡二叉树的判定

下图为一棵平衡二叉树：
而下图则不是：
原因是以8为根节点的子树的高度为4，而以18为结点的子树高度为2，两者的高度差为2大于1，所以其不是平衡二叉树。
如下也不是一棵平衡二叉树：
因为结点2的左子树高度为2，右子树高度为0，两者之差的绝对值大于1。
我们可以通过LeetCode题目110. Balanced Binary Tree来练习使用程序来判定一棵给定的二叉树是否为平衡二叉树，代码如下：
1
class Solution {
2
​
3
int depth(TreeNode *root)
4
{
5
if (!root)
6
{
7
return 0;
8
}
9
return std::max(depth(root->left) + 1, depth(root->right) + 1);
10
}
11
public:
12
bool isBalanced(TreeNode* root) {
13
return !root ||
14
std::abs(depth(root->left) - depth(root->right)) < 2 &&
15
isBalanced(root->left) && isBalanced(root->right);
16
}
17
};
Copied!

0x02 平衡二叉树的插入

平衡二叉树插入的基本思想是：每次插入一个结点时，都要检查其插入路径上的结点是否因为此次操作而导致不平衡，如果导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子绝对值大于1的结点，再对以此结点为根节点的子树，在保证二叉排序树特性的前提下，调整各节点之间的位置关系，使之重新达到平衡。
步骤如下：
将我们新插入的结点记为w
  • 首先按照二叉排序树的插入流程来插入结点w
  • 从w开始，向上遍历并找到第一个导致此树不平衡的结点z，将从结点z到结点w路径上的z的孩子记为y，将此路径上的z的孙子结点记为x
  • 对以z为根节点的子树进行旋转使整个树重新趋于平衡，有如下4种可能的情况
    • y是z的左孩子且x是y的左孩子，执行LL平衡旋转（右单旋转或Left Left Case），如下 ：
      1
      T1, T2, T3 and T4 are subtrees.
      2
      z y
      3
      / \ / \
      4
      y T4 Right Rotate (z) x z
      5
      / \ - - - - - - - - -> / \ / \
      6
      x T3 T1 T2 T3 T4
      7
      / \
      8
      T1 T2
      Copied!
    • y是z的左孩子且x是y的右孩子，执行LR平衡旋转（先左后右双旋转或Left Right Case），如下 ：
      1
      z z
      2
      / \ / \
      3
      y T4 Left Rotate (y) x T4
      4
      / \ - - - - - - - - -> / \
      5
      T1 x y T3
      6
      / \ / \
      7
      T2 T3 T1 T2
      8
      x
      9
      / \
      10
      Right Rotate(z) y z
      11
      - - - - - - - -> / \ / \
      12
      T1 T2 T3 T4
      Copied!
    • y是z的右孩子并且x是y的右孩子，执行RR平衡旋转（左单旋转或Right Right Case），如下：
      1
      z y
      2
      / \ / \
      3
      T1 y Left Rotate(z) z x
      4
      / \ - - - - - - - -> / \ / \