Binary tree traversal - recursive and iterative templates

Foreword of binary tree 、 Middle preface 、 Iteration and recursion of subsequent traversal , One template, one catch

1. recursive

   1. The former sequence traversal

   class Solution {
   public:
       vector<int> preorderTraversal(TreeNode* root) {
           vector<int> pre_res;
           preorder(root,pre_res);
           return pre_res;  
   
       }
       void preorder(TreeNode* root ,vector<int> & res){
           if(root == nullptr){
               return;
           }
           res.emplace_back(root->val);
           preorder(root->left,res);
           preorder(root->right,res);
       }
   };
   

   2. In the sequence traversal

   class Solution {
   public:
       void ldr(TreeNode* root, vector<int> & res ){
           if (root==nullptr)
               return ;
           ldr(root->left , res);
           res.push_back(root -> val);
           ldr(root ->right , res);
       }
       vector<int> inorderTraversal(TreeNode* root) {
           vector<int> res;
           ldr(root,res);
           return res;
       }
   };
   

   3. After the sequence traversal

   class Solution {
   public:
       vector<int> postorderTraversal(TreeNode* root) {
           vector<int> res;
           postorder(root,res);
           return res;
       }
       void postorder(TreeNode* root, vector<int>& res){
           if(root==nullptr) return ;
           postorder(root->left,res);
           postorder(root->right,res);
           res.emplace_back(root->val);
       }
   };
   

2. iteration

   1. The former sequence traversal

   class Solution {
   public:
       vector<int> postorderTraversal(TreeNode* root) {
           vector<int> res;
           postorder(root,res);
           return res;
       }
       void postorder(TreeNode* root, vector<int>& res){
           if(root==nullptr) return ;
           postorder(root->left,res);
           postorder(root->right,res);
           res.emplace_back(root->val);
       }
   };
   

   2. In the sequence traversal

   class Solution {
   public:
       vector<int> inorderTraversal(TreeNode* root) {
           vector<int> res;
           TreeNode* cur = root;
           stack<TreeNode*> s;
           while(s.size() || cur!=nullptr){
               while(cur){
                   s.push(cur);
                   cur = cur->left;
               }
               TreeNode* temp = s.top();
               s.pop();
               res.emplace_back(temp->val);
               cur =temp->right;
           }
           return res;
       }
   };
   

   3. After the sequence traversal
      It is obtained by modifying the previous sequence during subsequent traversal ：
      Preorder traversal order ： Around the middle ;
      Exchange the left and right traversal order to get ： Center right left ;
      Output the result list in reverse order, i.e ： Right and left ;

   class Solution {
   public:
       vector<int> postorderTraversal(TreeNode* root) {
           vector<int> res;
           stack<TreeNode*> s;
           TreeNode* cur =root;
           while(s.size() || cur!=nullptr ){
               while(cur){
                   res.emplace_back(cur->val);
                   s.push(cur);
                   cur = cur->right;
               }
               TreeNode* temp = s.top();
               s.pop();
               cur = temp->left;
   
           } 
           reverse(res.begin(),res.end());
           return res;
       }
   };