Leetcode-二叉树的前,中,后序的非递实现

Leetcode-二叉树的前,中,后序的非递实现

二叉树的前,中,后序的非递实现

前序的非递归中序的非递归后序的非递归

前序的非递归

借助力扣的题来实现前序遍历的非递归。前序的递归是先访问根节点，左子树，右子树。

二叉树的前序遍历链接

虽然递归实现较简单，但是非递归的实现我们也要掌握。非递归实现要借助栈来显示，但是思想还是递归的思想。
实现思路：
1.先访问左路节点
2.访问左路结点的同时入栈
3.子问题的方式再去访问右子树
先画一手图：

动图演示(借用力扣官方的动图)：

在附上代码：

 class Solution {
public:   
    vector preorderTraversal(TreeNode* root) {    
      vector res; //存val值
      stackst;//定义一个栈
            
      TreeNode* cur = root;//cur指向谁就开始访问谁

      while(cur || !st.empty()) //当cur为空或者栈为空循环结束
      {
          while(cur)
          {
            res.push_back(cur->val);//把值存到vector
            st.push(cur);   //入栈
            cur=cur->left; 
          }
        
           TreeNode* top = st.top();//取栈顶结点
           st.pop();

           //访问右子树交给子问题的方式解决 
           cur=top->right;
      }
       //最后返回vector
       return res;
    }
};

中序的非递归

有了前序的基础的话，中序的非递归也就变得简单了。中序遍历是左子树，根节点，右子树。
先让左路结点入栈，入栈完毕，取栈顶元素访问。之后用同样的方法访问右子树。
画图分析：

动图(力扣的动图)：

代码：

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
      vector res;
      stackst;
      TreeNode* cur = root;

      while(cur || !st.empty())
      {
          while(cur)
          {
            
            st.push(cur);//现将结点入栈
            cur=cur->left;
          }
        
           TreeNode* top = st.top(); 
           res.push_back(top->val);//访问栈顶元素
           st.pop();

           cur=top->right;
      }

       return res;
    }
};

后序的非递归

后序的遍历，左子树->右子树->根节点。左路结点先入栈，当右子树为空或右子树访问过了，栈顶结点出栈并访问。若栈顶结点的右子树还没访问，在用同样的方式访问右子树。
具体步骤：
1.左路结点入栈
2.观察栈顶结点
3.栈顶结点的右子树为空或者访问完右子树，访问栈顶结点。栈顶结点出栈，并记录栈顶结点
4.栈顶结点的右子树若没访问，则准备访问右子树
画图分析：

动图演示(取自力扣动图):

代码：

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        vector res;
        stackst;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);//左路结点先入栈
                cur = cur->left;
            }
            TreeNode* top = st.top();
            //右子树为空，或者栈顶的右子树是根节点则可以访问根节点
            if(top->right == nullptr || top->right == prev)
            {
                res.push_back(top->val);
                st.pop();
                prev = top;//记录栈顶结点
            }
            else
            {
                cur = top->right;
            }
        }
        return res;
    }
};