二叉树的三种遍历的非递归实现

前序遍历

• 主要思路是先将根节点入栈，然后每次循环从栈顶取出元素输出，同时将该元素的右节点和左节点压入栈中

  class Solution {
  public:
      vector<int> preorderTraversal(TreeNode* root) {
          if(!root)return vector<int>();
          
          stack<TreeNode*> s;
          s.push(root);
          TreeNode* temp;
          vector<int> ret;
          while(!s.empty())
          {
              temp = s.top();
              s.pop();
              ret.push_back(temp->val);
              if(temp->right)s.push(temp->right);
              if(temp->left)s.push(temp->left);
          }
          return ret;
      }
  };

  中序遍历

• 主要思路是新建一个结构体，结构体包括二叉树的节点指针信息和是否被访问过的标记信息，标记默认是false

  typedef struct nodeStruct
  {
      TreeNode* p; 
      bool flg; 
      nodeStruct(TreeNode* ptr):p(ptr),flg(false){}    
      nodeStruct(TreeNode* ptr, bool flag):p(ptr),flg(flag){}   
  } nodeS;

• 每次从栈顶取出一个元素，如果该元素的标记提示被访问过，那么直接将元素输出
• 如果该元素没有被访问过，那么现将该元素的访问标记置为true，然后将该元素的右子节点压入栈中，然后将节点自己压入栈中，最后将左子节点压入栈中

  typedef struct nodeStruct
  {
      TreeNode* p; 
      bool flg; 
      nodeStruct(TreeNode* ptr):p(ptr),flg(false){}    
      nodeStruct(TreeNode* ptr, bool flag):p(ptr),flg(flag){}   
  } nodeS;
  
  class Solution {
  public:
      vector<int> inorderTraversal(TreeNode* root) {
          if(!root)return vector<int>();
          vector<int> ret;
          stack<nodeS> s;
          s.push(nodeS(root));
          nodeS temp(NULL);
          while(!s.empty())
          {
              temp = s.top();
              s.pop();
              if(!temp.flg)
              {
                  if(temp.p->right)s.push(nodeS(temp.p->right));
                  temp = nodeS(temp.p, true);
                  s.push(temp);
                  if(temp.p->left)s.push(nodeS(temp.p->left));
              }
              else
              {
                  ret.push_back(temp.p->val);
              }
          }
          return ret;
      }
  };

##后序遍历

• 结构体方法同上，跟之前的主要区别是针对没有访问过的节点需要先将自己压入栈中，然后再将右节点和左节点压入栈中

  typedef struct
  stackUnit{
      TreeNode* p;
      bool flg;
      stackUnit(TreeNode* ptr, bool flag):p(ptr), flg(flag){}
  } nodeS;
  class Solution {
  public:
      vector<int> postorderTraversal(TreeNode* root) {
          if(!root)return vector<int>();
          vector<int> v;
          stack<nodeS> s;
          s.push(nodeS(root, false));
          nodeS temp(NULL, false);
          while(!s.empty())
          {
              temp = s.top();
              s.pop();
              if(temp.flg)
              {
                  v.push_back(temp.p->val);
              }
              else
              {
                  s.push(nodeS(temp.p, true));
                  if(temp.p->right)s.push(nodeS(temp.p->right,false));
                  if(temp.p->left)s.push(nodeS(temp.p->left,false));
              }
          }
          return v;
      }
  };