【二叉树进阶】--- 前中后序遍历非递归
Welcome to 9ilk's Code World
(๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏： 算法Journey
本篇博客我们将来了解有关二叉树前中后序遍历的非递归版本。
🏠 前序遍历
要迭代非递归实现二叉树的前序遍历，首先还是要借助递归的类似思想，只需要把结点存在栈中，方便类似递归回退时取出父路径结点。跟这里不同的是，我们把一颗二叉树分为两个部分：1. 左路结点 2. 左路结点的右子树。
- 我们先访问左路结点将他们依次入栈，再依次访问左路结点的右子树。
- 访问左路结点的右子树只需要我们从栈里面取出左路结点，由于右子树又可以分为左路结点和右子树，所以我们以循环子问题的思想访问左路结点的右子树。
参考代码：
class Solution {
public:vector<int> ret;vector<int> preorderTraversal(TreeNode* root){TreeNode* cur = root;stack<TreeNode*> st;while(cur || !st.empty()){//访问左路节点while(cur) {st.push(cur);ret.push_back(cur->val)cur = cur->left;}//从栈中取左路节点依次访问他们右子树TreeNode* top = st.top();st.pop();cur = top->right; }return ret; }
};🏠 中序遍历
中序跟前序其实思路完全一致，只是访问根的时机不同。中序是对左路结点时不能先访问，而是先依次入栈，入栈完左路结点后再访问这些左路结点，再依次访问他们各自的右子树。
参考代码：
class Solution {
public:vector<int> ret;vector<int> inorderTraversal(TreeNode* root) {TreeNode* cur = root;stack<TreeNode*> st;while(cur || !st.empty()){//访问左路节点while(cur) {st.push(cur); //先入栈不访问cur = cur->left;}TreeNode* top = st.top();ret.push_back(top->val);//访问st.pop();cur = top->right; //访问右子树}return ret; }
};🏠 后序遍历
后序跟前序的思路也是完全一致，毕竟模拟的是递归展开过程，只不过后序是左子树-右子树-根，最后再访问根结点，也就是说要左右子树都访问完之后才能访问根并出栈。
TreeNode* top = st.top();
if(top->right == nullptr)
{ret.push_back(top->val);st.pop();
}
else //访问右子树
{cur = top->right;
}当我们还面临一个问题当取到左路结点的右子树时，我们需要想办法标记判断右子树是否已经访问过了，如果访问过就直接访问根，没有访问过就访问右子树。因此我们上述逻辑访问右子树时不知道是否已经访问过右子树，处理完右子树后上一层的结点没有pop掉再次判断，因此会陷入循环。
解决方法是用一个prev变量来记录上一个访问的结点。但我们需要明白以下逻辑：
1. 取到一个左路结点时，左子树已经访问过了。
2.如果左路节点右子树不为空，右子树没有访问，那么上一个访问节点是左子树的根，此时需要访问右子树。
3.如果左路节点右子树不为空，右子树已经访问过，那么上一个访问节点应该是右子树的根，此时需要访问根。
4.如果左路节点右子树为空，此时说明左子树已经访问，右子树不需要访问，此时需要访问根。
参考代码：
class Solution {
public:vector<int> ret;vector<int> postorderTraversal(TreeNode* root) {TreeNode* cur = root;stack<TreeNode*> st;TreeNode* pre = nullptr;while(cur || !st.empty()){//访问左路节点while(cur) {st.push(cur);cur = cur->left;}// 这时代表左子树已经访问过了TreeNode* top = st.top();if(top->right == nullptr || top->right == pre)右子树为空或右子树已经访问完才访问根{ret.push_back(top->val);st.pop(); pre = top;}elsecur = top->right; //右子树没访问再循环子问题访问右子树}return ret; }
};完。