二叉树理论基础
二叉树种类
1. 满二叉树
如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
如图所示：
这棵二叉树为满二叉树，也可以说深度为k（从1开始），有2^k-1个节点的二叉树。
2. 完全二叉树
什么是完全二叉树？
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。
如图所示：
之前我们刚刚讲过优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。
3. 二叉搜索树
前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
下面这两棵树都是搜索树
4. 平衡二叉搜索树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
如图所示：
C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn（二分法），注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表。
所以大家使用自己熟悉的编程语言写算法，一定要知道常用的容器底层都是如何实现的，最基本的就是map、set等等，否则自己写的代码，自己对其性能分析都分析不清楚！
二叉树的存储方式
二叉树可以链式存储，也可以顺序存储。
那么链式存储方式就用指针，顺序存储的方式就是用数组。
顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。
链式存储如图：
链式存储是大家很熟悉的一种方式，那么我们来看看如何顺序存储呢？
其实就是用数组来存储二叉树，顺序存储的方式如图：
如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。
二叉树的遍历方式
二叉树主要有两种遍历方式：
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 广度优先遍历：一层一层的去遍历。
这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候 还会介绍到。
那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：
- 深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历
- 层次遍历（迭代法）
这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式
- 前序遍历：中左右
- 中序遍历：左中右
- 后序遍历：左右中
大家可以对着如下图，看看自己理解的前后中序有没有问题。
二叉树的定义
刚刚我们说过了二叉树有两种存储方式顺序存储，和链式存储，顺序存储就是用数组来存，这个定义没啥可说的，我们来看看链式存储的二叉树节点的定义方式。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
二叉树的定义和链表是差不多的，相对于链表，二叉树的节点里多了一个指针， 有两个指针，指向左右孩子。
二叉树的递归遍历
题目链接：144.二叉树的前序遍历 145.二叉树的后序遍历 94.二叉树的中序遍历
文档讲解：代码随想录
状态：二叉树简单的遍历AC
思路
递归三板斧：
1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
本题在实现遍历时，根据函数返回类型以及参数可以灵活给出递归解法
题解
//前序遍历
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v1,v2,v3;
if (root == nullptr)return v3;
v3.push_back(root->val);
v1 = preorderTraversal(root->left);
v2 = preorderTraversal(root->right);
if(!v1.empty())v3.insert(v3.end(),v1.begin(),v1.end());
if(!v2.empty())v3.insert(v3.end(),v2.begin(),v2.end());
return v3;
}
};
//中序遍历
class Solution {
public:
void traversal(TreeNode *cur, vector<int> &vec)
{//推荐这一种，省去了vector的拼接
if(cur == nullptr)return;
//中序遍历
traversal(cur->left, vec);
vec.push_back(cur->val);
traversal(cur->right, vec);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root,result);
return result;
}
};
//后序遍历
class Solution {
public:
void traversal(TreeNode *cur, vector<int> &vec)
{
if(cur == nullptr)return;
//后序遍历
traversal(cur->left, vec);
traversal(cur->right, vec);
vec.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root,result);
return result;
}
};
二叉树的迭代遍历
题目链接：144.二叉树的前序遍历 145.二叉树的后序遍历 94.二叉树的中序遍历
文档讲解：代码随想录
状态：不会，比较难理清
思路
用栈的方式去模拟递归，以前序遍历说明：
//前序遍历：中左右
vec.push_back(cur->val);
//将当前状态保存压栈，遍历左子树
traversal(cur->left, vec);
//当左子树全部遍历完（即左节点的全部左右子树），弹栈到根节点时进行右子树遍历
traversal(cur->right, vec);
故流程如下：
1. 读取状态
2. 压栈保存根状态
3. 左子树空了，弹栈去非空右子树
4. 全部弹栈完毕，结束
题解
//前序遍历,严格按照递归思路
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stk;
TreeNode* node = root;
while(node != nullptr)
{ //中左右-中，直接将根加入解集
result.push_back(node->val);
stk.push(node);
//中左右-左
node = node->left;
//左子树为空
while(node == nullptr && !stk.empty())
{
//类似于return回溯
node = stk.top();
stk.pop();
//中左右-右
node = node->right;
}
}
return result;
}
};
//中序遍历,严格按照递归思路
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stk;
TreeNode* node = root;
while(node != nullptr)
{
//左中右-左，向左搜索，并保存入栈
//并非要读取信息
stk.push(node);
node = node->left;
//左子树为空时，回溯，这时候读取信息
while(node==nullptr && !stk.empty())
{
node = stk.top();
stk.pop();
//左中右-中，直接将根加入解集
result.push_back(node->val);
//左中右-右，遍历非空右子树
node = node->right;
}
}
return result;
}
};
//后序遍历，因为要两个压栈，不如操作前序遍历
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stk;
TreeNode* node = root;
while(node!=nullptr)
{
result.push_back(node->val);
stk.push(node);
node = node->right;
while(node == nullptr && !stk.empty())
{
node = stk.top();
stk.pop();
node = node->left;
}
}
reverse(result.begin(),result.end());
return result;
}
};//前序遍历左右呼唤并且reverse即可，可举例理解
二叉树的层序遍历
题目链接：我要打十个
102.二叉树的层序遍历
107.二叉树的层次遍历II
199.二叉树的右视图
637.二叉树的层平均值
429.N叉树的层序遍历
515.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
111.二叉树的最小深度
文档讲解：代码随想录
状态：学习层序遍历轻松AC，个别题目使用递归
思路
层序遍历，使用队列做文章，数据结构与算法中学过
题解
//这里给出标准层序遍历的代码
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> que;
if(root!= nullptr)que.push(root);
while(!que.empty())
{
int size = que.size();
vector<int> temp;
while(size--)
{
temp.push_back(que.front()->val);
if(que.front()->left)que.push(que.front()->left);
if(que.front()->right)que.push(que.front()->right);
que.pop();
}
res.push_back(temp);
}
return res;
}
};