【二叉树进阶】--- 前中后序遍历非递归

 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;
            }
            else
            cur = top->right;    //右子树没访问再循环子问题访问右子树
         }
       return ret;     
    }
};

完。