Iterative version of preorder traversal, inorder traversal, and postorder traversal of binary tree

二叉树前序遍历、中序遍历、Iterative version of post-order traversal

1. 前序遍历

void preorder(TreeNode* root)
{
    
      if(root==NULL)
           return;
      stack<TreeNode*> s;
      while(root||!s.empty())
      {
    
              while(root)
              {
    
                     //...处理root
                     s.push(root);
                     root=root->left;
              } 
              root=s.top();
              s.pop();
              root=root->right; 
      }
}

2. 中序遍历

void midorder(TreeNode* root)
{
    
        if(root)
            cout<<"empty!"<<endl;
        stack<int> s;
        while(root||!s.empty())
        {
    
                while(root)
                {
    
                	s.push(root);
                	root=root->left; 
                }
                root=s.top();
                s.pop();
                //...处理root
                root=root->right;
        }
}

3. 后序遍历

void postorder(TreeNode* root) 
{
    
        stack<TreeNode*> s;
        TreeNode * p = root;
        TreeNode * lastVisited = NULL;//Record the last visited node
        
        if(p == NULL)
            return ans;
        
        while(!s.empty() || p)
        {
    
        	//Keep iterating to the left child,直到左孩子为空,At the same time, the nodes on the path are pushed onto the stack
            if(p)
            {
    
                s.push(p);
                p = p->left;
            }
            //此时p==NULL,Reached the lower left corner node
            else
            {
    
                p = stk.top();
                //右孩子为空,Or the right child has already visited the last time
                if(p->right == NULL || p->right == lastVisited)
                {
    
                    //...处理p
                    lastVisited = p;//更新lastVisited
                    s.pop();
                    p = NULL;
                }
                else{
    
                    p = p->right;//这时p是第一次被访问,The value it points to cannot be accessed directly,should visit the right subtree first
                }
            }
        }
        
        return ans;
    }

	Preorder traversal is basically the same as inorder traversal,The access node location is different,Post-order traversal is relatively complex,关键在于lastvisited的追踪.