Middle order traversal of Li Kou 94 binary tree

Power button 94 Middle order traversal of binary trees

Title Description

Given the root node of a binary tree root , return its Middle preface Traverse . Advanced : The recursive algorithm is very simple , Can you do it by iterative algorithm ？

Input / output details

 Input ：root = [1,null,2,3]
 Output ：[1,3,2]

 Input ：root = []
 Output ：[]

 Input ：root = [1]
 Output ：[1]

Algorithm 1, Use recursion to complete the middle order , Before the order , After the sequence traversal

// Use the idea of recursion , In the sequence traversal 
        vector<int>inorderTraversal(TreeNode*root)
        {
    
            if(root==nullptr)
            {
    
                return res;
            }
            inorderTraversal(root->left);
            res.push_back(root->val);
            inorderTraversal(root->right);
            return res;
        }
        // The former sequence traversal , Store the root node first and then the left node , Then the right node 
        vector<int>preOrderTraversal(TreeNode*root)
        {
    
            if(root==nullptr)
            {
    
                return res;
            }
            res.push_back(root->val);
            preOrderTraversal(root->left);
            preOrderTraversal(root->right);
            return res;
        }
        // After the sequence traversal , First left, then right, and finally root 
        vector<int>postOrderTraversal(TreeNode*root)
        {
    
            if(root==nullptr)
            {
    
                return res;
            }
            postOrderTraversal(root->left);
            postOrderTraversal(root->right);
            res.push_back(root->val);
            return res;
        }

Algorithm 2, Use the stack for iterative computation

// Use iterations and stacks to implement 
        vector<int>inorderTraversal2(TreeNode*root)
        {
    
            vector<int>res;
            // Build a stack to save the current node 
            stack<TreeNode*>stk;
            // When a node exists , And the stack is not empty 
            while(root!=nullptr||!stk.empty())
            {
    
                while(root!=nullptr)
                {
    
                    stk.push(root);
                    // When the node is not empty, the node moves to the left 
                    root=root->left;
                }
                // When root When the current value is empty , Then move it to the right , And put the value in the queue 
                root=stk.top();
                stk.pop();
                res.push_back(root->val);
                root=root->right;
            }
            return res;
        }

Algorithm 3, Use Morris middle order to traverse

 // Use Morris method to implement 
     vector<int>inorderTraversal3(TreeNode*root)
     {
    
        vector<int>res;
        TreeNode*preDecessor=nullptr;

        while(root!=nullptr)
        {
    
            if(root->left!=nullptr)
            {
    
                //preDecessor Node is the current root The node goes a little to the left , Then go straight to the right until you can't reach it 
                preDecessor=root->left;
                // When preDecessor When the right node of exists and is not equal to the root node ,preDecessor Move all the way to the right 
                while (preDecessor->right!=nullptr&&preDecessor->right!=root)
                {
    
                    preDecessor=preDecessor->right;
                }
                // If preDecessor Right pointer to , Continue to traverse the left subtree 
                if(preDecessor->right==nullptr)
                {
    
                    preDecessor->right=root;
                    root=root->left;
                }

                // At this point, the left subtree has been accessed , disconnect 
                else{
    
                    res.push_back(root->val);
                    preDecessor->right=nullptr;
                    root=root->right;
                }
                
            }
            else{
    
                res.push_back(root->val);
                root=root->right;
            }
        }
        return res;
     }