代码随想录算法训练营Day14|二叉树理论基础及其递归遍历和迭代遍历
目录
二叉树理论基础
二叉树的种类
二叉树可分为满二叉树和完全二叉树，二叉搜索树和平衡二叉搜索树等。
满二叉树
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。若满二叉树的深度为k，则有2^k-1个节点。
完全二叉树
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置（从左到右节点连续）。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。
满二叉树是完全二叉树的一种特殊情况，堆也是一棵完全二叉树，同时保证父子节点的顺序关系。
二叉搜索树
前面两种树都是没有数值的，而二叉搜索树是有数值的，二叉搜索树是一个有序树。它具有以下特点：
- 若左子树不为空，则左子树上的所有节点值均小于根节点（中间节点）的值；
- 若右子树不为空，则右子树上的所有节点值均大于根节点（中间节点）的值；
- 它的左右字数也分别为二叉排序树，即满足以上两条。
平衡二叉搜索树
在二叉搜索树的基础上加上左右两个字数的高度差绝对值不超过1的条件。
C++中map、set|、multimap、multiset的底层实现都是平衡二叉搜索树，map、set的增删时间复杂度都是logn（unordered_map，unordered_set底层实现是哈希表）。
二叉树的存储方式
二叉树可以链式存储，也可以顺序存储。
链式存储用指针，顺序存储用数组。用数组来存储二叉树时，若父节点的下标是i，则他的左孩子是i * 2 + 1，右孩子就是i * 2 + 2。但是一般用链式表示二叉树更方便。
二叉树的遍历方式
二叉树的两种遍历方式：
1.深度优先遍历：先往深走，遇到叶子节点再往回走。
2.广度优先遍历：一层一层地去遍历。
继续对两种遍历进行拓展：
- 深度优先遍历
前序遍历：中左右（递归法，迭代法）
中序遍历：左中右（递归法，迭代法）
后序遍历：左右中（递归法，迭代法）
- 广度优先遍历
层次遍历（迭代法）
在深度优先遍历中有三个顺序：前中后序，前中后指的是中间节点的遍历顺序。
在实现深度优先遍历时，经常使用递归的方式，栈也是递归的一种实现结构，因此前中后序遍历的逻辑也可以借助栈使用递归的方式实现。
而广度优先遍历的实现一般使用队列来实现。这是由队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层地遍历二叉树。
二叉树的定义
链式存储二叉树节点的定义方式如下：
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL){}
};二叉树的定义和链表类似，只是二叉树的节点多了一个指针，指向左右孩子。
二叉树的递归遍历
本节介绍二叉树前中后序的递归写法。写递归算法遵循的三要素：
- 确定递归函数的参数和返回值；
- 确定终止条件；
- 确定单层递归的逻辑。
以144.二叉树的前序遍历、94.二叉树的中序遍历、145.二叉树的后序遍历为例进行二叉树的递归实现。
前序遍历（递归实现）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& ver){ //1.确定递归参数的参数和返回值
if (cur == NULL) return; //2.确定终止条件
//3.确定单层递归的逻辑
ver.push_back(cur->val); //中
traversal(cur->left, ver); //左
traversal(cur->right, ver); //右
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};中序遍历（递归实现）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec){
if (cur == NULL) 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;
}
};后序遍历（递归实现）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec){
if (cur == NULL) 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;
}
};中序遍历和后序遍历在前序遍历的基础上只需要更改递归函数中单词递归中左右的顺序即可实现。
二叉树的迭代遍历
通过先前栈与队列的题目学习，我们知道匹配问题都是栈的强项，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回值等压入调用栈中。然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归可以返回上一层位置的原因。
因此用栈也可以实现二叉树的前中后序遍历。
前序遍历（迭代法）
前序遍历是中左右，每次先处理中间节点，将根节点放入栈中，在将右孩子放入栈中，再加入左孩子，这样使得出栈时是中左右的顺序。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root == NULL) 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);
if (cur->left) st.push(cur->left);
}
return result;
}
};后序遍历（迭代法）
后序遍历可以利用前序遍历的代码，更改前中后序的实现顺序然后进行反转，巧妙实现。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root == NULL) return result;
st.push(root);
while (!st.empty()){
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
if (node->left) st.push(node->left);
if (node->right) st.push(node->right);
}
reverse(result.begin(), result.end());
return result;
}
};中序遍历（迭代法）
使用迭代法进行中序遍历不能直接再在前序遍历的代码上进行修改，需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != NULL || !st.empty()){
if (cur != NULL){
st.push(cur);
cur = cur->left;
}else{
cur = st.top();
st.pop();
result.push_back(cur->val);
cur = cur->right;
}
}
return result;
}
};在使用迭代法尽心遍历时，前序和中序的遍历算法并不统一，因为前序遍历访问节点和处理节点可以同步处理，而中序就无法做到同步。
二叉树统一迭代法
上文提到使用栈时，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
那么将访问的节点放入栈中，把要处理的节点也放入栈中，但是另做标记。将要处理的节点放入栈之后，紧接着放入一个空指针作为标记。（这种方法也叫标记法）。
中序遍历（标记法）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root == NULL) return result;
st.push(root);
while (!st.empty()){
TreeNode* node = st.top();
if (node != NULL){
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();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};前序遍历（标记法）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root == NULL) return result;
st.push(root);
while (!st.empty()){
TreeNode* node = st.top();
if (node != NULL){
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();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};后序遍历（标记法）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root == NULL) return result;
st.push(root);
while (!st.empty()){
TreeNode* node = st.top();
if (node != NULL){
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();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};总结
本文主要介绍了二叉树的基础和遍历方式，知识点较多，需要多次回顾复习，尤其是二叉树的递归遍历尤其重要，是展开后序题目的基础，通过力扣上三道基础题的练习，要熟练掌握二叉树前中后序的递归遍历和迭代遍历！