二叉树种类
满二叉树
层数为n，节点数为\(2^n-1\)的二叉树
完全二叉树
除了底层都是满的，底层不一定满，但是从左到右连续
二叉搜索树
按一定顺序排列的二叉数，如某节点左侧节点全部小于该节点，右侧节点全部大于该节点，搜索时间复杂度为\(O(logn)\)
平衡二叉搜索树
左子树与右子树高度差绝对值不大于1的二叉搜索树
map, set, multimap, multiset底层实现都为平衡二叉搜索树
二叉树储存方式
二叉树可以使用线性储存或链式储存，一般会使用链式
链式储存
与链表类似，二叉树的每一个节点都包含三个变量
- 节点储存的值
- 指向左子树的指针
- 指向右子树的指针
通过最根部的头指针，就能找到其所有的子节点
线性储存
不太常见，但也可以使用。类似于将树存入数组，每一个节点都给一个对应的下标\(i\), 下标为\(i\)的节点的左边子节点下标为\(2i+1\)，右边子节点下标为\(2i+2\)。 若该节点不存在，可以存null
二叉树遍历方式
深度优先搜索
一般使用递归来实现，但是也可以使用栈，迭代法来实现
前中后序遍历指的是根节点遍历的位置，即“中”第几个遍历。
前序遍历
中 左 右
中序遍历
左 中 右
后续遍历
左 右 中
广度优先搜索
层序遍历
即迭代法，一般使用队列，先进先出，一层一层的去遍历。
二叉树定义
一般包括
- 值
- 左指针
- 右指针
- 构造函数
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
递归遍历
lc144 二叉树的前序遍历
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root,result);
return result;
}
private:
void traversal(TreeNode* cur, vector<int>& v){
if(cur == NULL){
return;
}
v.push_back(cur->val); //中
traversal(cur->left,v); //左
traversal(cur->right,v); //右
}
};
lc145 二叉树的后序遍历
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root,result);
return result;
}
void traversal(TreeNode* cur, vector<int>& v){
if (cur == NULL){
return;
}
traversal(cur->left,v); //左
traversal(cur->right,v); //右
v.push_back(cur->val); //中
}
};
lc94 二叉树的中序遍历
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root,result);
return result;
}
void traversal(TreeNode* cur, vector<int>& v){
if (cur == NULL){
return;
}
traversal(cur->left,v); //左
v.push_back(cur->val); //中
traversal(cur->right,v); //右
}
};
迭代法遍历
对前中后序遍历使用迭代法可以使用栈，注意将想要后处理的节点先压入栈
lc144 二叉树的前序遍历
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(root==nullptr) return result;
st.push(root);
while(!st.empty()){
TreeNode* cur = st.top();
st.pop();
result.push_back(cur->val); //中
if(cur->right) st.push(cur->right); //右不为空压入栈，stack先进后出
if(cur->left) st.push(cur->left); //左不为空压入栈
}
return result;
}
};
lc145 二叉树的后序遍历
后续遍历迭代法只需要在前序遍历的基础上更改左右子节点压入栈的顺序，并且返回反转数组即可完成。前序遍历的顺序是中左右，更改压入栈顺序后为中右左，反转数组后为左右中，即后序遍历顺序
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(root==nullptr) return result;
st.push(root);
while(!st.empty()){
TreeNode* cur = st.top();
st.pop();
result.push_back(cur->val); //中
if(cur->left) st.push(cur->left); //先压入左节点，即后处理左节点
if(cur->right) st.push(cur->right); //后压入右节点，即先处理右节点
}
reverse(result.begin(),result.end());
return result;
}
};
lc94 二叉树的中序遍历
需要处理的节点顺序和遍历顺序不一样
需要使用一个指针来记录当前遍历位置，栈来记录遍历过的节点
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
TreeNode* cur;
stack<TreeNode*> st;
cur = root;
while(cur!=nullptr||!st.empty()){
if(cur!=nullptr){
st.push(cur);
cur = cur->left;
}
else{
cur = st.top();
st.pop();
result.push_back(cur->val);
cur = cur->right;
}
}
return result;
}
};
统一风格的前中后序迭代法遍历
使用上面的方法，前后序遍历我们使用栈来进行遍历，中序使用指针来进行遍历，这样代码风格不太统一（与递归方法比较）。一个统一方法是使用栈中的空值来标记遍历过却没有处理的节点，在需要暂时跳过不处理（只检查其左右子节点是否存在，并添加进栈，不弹出或加入返回数组）的节点后面压入一个空值，用于记录。
在修改遍历顺序时，只需要调换几行代码的顺序即可
lc144 二叉树的前序遍历
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(root==nullptr) return result;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
//不为空值，说明第一次遍历到，需要查看其左右子节点，排好顺序，栈为逆序
//重新加入stack，并在其后面压入NULL表示已经遍历过，下次可以直接加入返回数组
if(node){
st.pop();
if(node->right) st.push(node->right); //右
if(node->left) st.push(node->left); //左
st.push(node); //中
st.push(NULL); //中后面压入空值，进行标记
}
//发现空值，则栈中空值下一个节点已经被遍历过，直接加入返回数组即可
else{
st.pop(); //弹出空值
node = st.top();
result.push_back(node->val);
st.pop(); //弹出加入过返回数组的值
}
}
return result;
}
};
lc145 二叉树的后序遍历
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(root==nullptr) return result;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
//不为空值，说明第一次遍历到，需要查看其左右子节点，排好顺序，栈为逆序
//重新加入stack，并在其后面压入NULL表示已经遍历过，下次可以直接加入返回数组
if(node){
//st.pop();
//st.push(node); //中
st.push(NULL); //中后面压入空值，进行标记
if(node->right) st.push(node->right); //右
if(node->left) st.push(node->left); //左
}
//发现空值，则栈中空值下一个节点已经被遍历过，直接加入返回数组即可
else{
st.pop(); //弹出空值
node = st.top();
result.push_back(node->val);
st.pop(); //弹出加入过返回数组的值
}
}
return result;
}
};
lc94 二叉树的中序遍历
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(root==nullptr) return result;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
//不为空值，说明第一次遍历到，需要查看其左右子节点，排好顺序，栈为逆序
//重新加入stack，并在其后面压入NULL表示已经遍历过，下次可以直接加入返回数组
if(node){
st.pop();
if(node->right) st.push(node->right); //右
st.push(node); //中
st.push(NULL); //中后面压入空值，进行标记
if(node->left) st.push(node->left); //左
}
//发现空值，则栈中空值下一个节点已经被遍历过，直接加入返回数组即可
else{
st.pop(); //弹出空值
node = st.top();
result.push_back(node->val);
st.pop(); //弹出加入过返回数组的值
}
}
return result;
}
};