前言
本文将讲述二叉树递归与迭代的相关知识。
🕺作者： 迷茫的启明星
专栏：【数据结构从0到1】
相关文章：《数据结构二叉树的链式存储讲解及前中后序遍历和层次遍历》😘欢迎关注：👍点赞🙌收藏✍️留言
🏇码字不易，你的👍点赞🙌收藏❤️关注对我真的很重要，有问题可在评论区提出，感谢阅读！！！
持续更新中~
1. 二叉树的递归遍历（一入递归深似海，从此offer是路人）
首先我们要知道递归的三要素是什么？
确定递归函数的参数和返回值
我们看到一个递归确定它在递归过程中需要处理哪些参数就需要加上那些，并且还要注意返回值是否合理
确定终止条件
我们需要判断递归什么时候停止，以及思考怎么停止
确定递归的逻辑
递归过程中的操作往往是重复的或者说是相似的，只是改变了一些参数
以二叉树前序遍历为例：
-
确定递归函数参数及返回值
参数里需要返回遍历情况的数组、树的节点
void traval(TreeNode* cur,vector<int> &result) -
确定终止条件
前序遍历上面时候停止呢？
在前序遍历的时候的顺序是”中左右“，也就是先访问当前节点，再访问左节点，左节点访问完了，直到遇到没有孩子的节点才返回，访问上一个节点的右节点，再访问左节点，左节点访问完了，直到遇到没有孩子的节点才返回，也就是说返回条件是节点为nullptr时。
if(cur==nullptr)return; -
确定递归逻辑
上面已经阐述了递归的逻辑，也就是先访问当前节点，再访问左节点和右节点。
result.push_back(cur->val); traval(cur->left,result); traval(cur->right,result);
由此我们已经完成了二叉树前序遍历的分析工作
那么代码如下，中序遍历和后序遍历逻辑同样如此就再啰嗦。
1.1 前序遍历
class Solution {
public:
void traval(TreeNode* cur,vector<int> &result)
{
if(cur==nullptr)return;
result.push_back(cur->val);
traval(cur->left,result);
traval(cur->right,result);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traval(root,result);
return result;
}
};
1.2 中序遍历
class Solution {
public:
void traval(TreeNode*cur,vector<int>& result)
{
if(cur==nullptr)return;
traval(cur->left,result);
result.push_back(cur->val);
traval(cur->right,result);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
traval(root,result);
return result;
}
};
1.3 后序遍历
class Solution {
public:
void traval(TreeNode*cur,vector<int> &result)
{
if(cur==nullptr)return;
traval(cur->left,result);
traval(cur->right,result);
result.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
traval(root,result);
return result;
}
};
2.二叉树的迭代遍历（听说递归能做的，栈也能做？）
为什么可以用栈来实现递归呢？
其实编译器在递归的时候本质就是在调用栈，当一个函数里面嵌套一个函数，在调用的时候，只有里面的函数都返回完了，这个函数才返回，也就是后进先出原则。
2.1 前序遍历
那么前序遍历的迭代是怎么一回事呢？
假如说有个二叉树是这样的：
它的迭代过程应该是这样的：
那么代码应该怎么表述呢？
- 首先应该建立一个存储顺序的数组，一个以树节点为元素的栈
- 然后需要判断树是否是空树，是则直接返回无元素数组
- 需要建立一个循环，但在循环开始前需要把树的根节点push进去
- 然后需要判断循环的停止条件是什么？根据上面图示可知只要栈不为空，循环就不会停止，于是循环的条件就是栈不为空
- 在循环里面需要一个变量来存储pop掉的节点
- 为了保持”中 左 右“的顺序就需要先让右节点先进，然后左节点进，以此保证左节点先弹出
代码如下：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(root==nullptr)return result;
st.push(root);
TreeNode* cur=nullptr;
while(!st.empty())
{
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;
}
};
2.2 中序遍历
前面我们实现了前序遍历的迭代法，但是中序遍历是否像递归那样只要交换顺序就可以了呢？并非如此
因为刚刚前序遍历时我们有两个操作：
- 处理：将元素放进result数组中
- 访问：遍历节点
它们在前序遍历时是同时发生的
但是中序遍历不同
中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
图示如下：
代码如下：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode*cur=root;
while(cur!=nullptr||!st.empty())
{
if(cur!=nullptr)
{
st.push(cur);
cur=cur->left;
}
else
{
cur=st.top();
result.push_back(cur->val);
st.pop();
cur=cur->right;
}
}
return result;
}
};
2.3 后序遍历
后序遍历相当于前序遍历的反面，就不画图了
只需要了解一下思路即可
- 声明一个栈，将根节点加入栈中；
- 初始化一个变量pre为null，表示上一个访问的节点；
- 若栈不为空，则进行如下操作：
- 取出栈顶元素top；
- 如果top没有左右孩子或者前一个访问的节点是其左孩子或右孩子，则访问该节点并将其弹出栈；
- 否则，先将其右孩子入栈，再将左孩子入栈，保证左孩子先弹出。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(root==NULL)return result;
TreeNode*cur=NULL;
TreeNode*pre=NULL;
st.push(root);
while(!st.empty())
{
cur=st.top();
if((cur->left==NULL&&cur->right==NULL)||
(pre!=NULL&&(pre==cur->left||pre==cur->right)))
{
result.push_back(cur->val);
st.pop();
pre=cur;
}
else
{
if(cur->right!=NULL)st.push(cur->right);
if(cur->left!=NULL)st.push(cur->left);
}
}
return result;
}
};
3. 二叉树的统一迭代法
前面所讲述的迭代法，前中后序遍历实现并不相同，因为他们对节点处理顺序和访问顺序不一致而造成的，那么有没有一种办法让他们能够像前面递归的方法那样，只需要改变几行代码就实现前中后迭代的切换呢？有的
既然无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法
代码如下：
3.1 中序遍历
代码中的 st.push(NULL); 的作用就是插入一个空指针作为标记，表示当前节点的左子树已经全部被访问过了，但是右子树还没有被访问，同时也表示这个节点已经被访问过一次，但是还没有处理过。当遍历到弹出这个空指针时，就说明当前节点的左子树已经全部被访问完了，可以处理这个节点了，于是就将这个节点弹出栈，将它的值加入到结果集中，并继续遍历它的右子树。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != NULL) 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;
}
};
3.2 前序遍历
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != NULL) 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;
}
};
3.3 后序遍历
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != NULL) 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;
}
};
你会发现的是，只需要改变两行代码就切换了功能，不过需要把思路捋清楚，忘了就再写一遍。
后记
本篇主要讲述了二叉树的递归遍历与迭代遍历，我们发现递归遍历只要交换代码实现的顺序就可以实现前中后遍历，而迭代法则需要限定不同的条件，这是因为处理顺序和访问顺序不一致而造成的，那么有没有办法统一它们呢？有的。我们实现了二叉树的迭代统一，自此二叉树的前中后序遍历我们就讲完了。
感谢大家支持！！！
respect！文章来源：https://www.toymoban.com/news/detail-442785.html
下篇见！
文章来源地址https://www.toymoban.com/news/detail-442785.html
到了这里，关于二叉树的递归遍历与迭代遍历（图示）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
