o(n)

Preorder

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        if(!root)
            return res;      
        stack<TreeNode *> s;

        while(!s.empty() || root){
            if(root){
                res.push_back(root->val);
                if(root->right)
                    s.push(root->right);        
                root = root->left;    
            }else{
                root = s.top();
                s.pop();
            }
        }
        return res;        
    }

 

Inorder

  vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        if(!root)
            return res;
        stack<TreeNode *>s;
        while(root || !s.empty()){
            if(root){
                s.push(root);
                root = root->left;
            }else{
                root = s.top();
                s.pop();
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }

 

Postorder

  vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if(!root)
            return res;
        stack<TreeNode *> s;
        TreeNode *prev = NULL;
        while(!s.empty() || root){
            if(root){
                s.push(root);
                root = root->left;
            }else{
                TreeNode *tmp = s.top();
                if(tmp->right && tmp->right !=prev)
                    root = tmp->right;
                else{
                    s.pop();                    
                    res.push_back(tmp->val);
                    prev = tmp;
                }
            }
        }
        return res;
    }

 

Double stack for postorder

  vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if(!root)
            return res;            
        stack<TreeNode *> container;
        stack<TreeNode *> resStack;
        container.push(root);

        while(!container.empty()){
            TreeNode *cur = container.top();
            resStack.push(cur);
            container.pop();            
            if(cur->left)
                container.push(cur->left);
            if(cur->right)
                container.push(cur->right);
        }   
        while(!resStack.empty()){
            res.push_back(resStack.top()->val);
            resStack.pop();
        }  
        return res;
    }

 

o(1)

Morris traverse:

Preorder

    vector<int> preorderTraversal(TreeNode *root) {
        // write your code here
        TreeNode *cur = root,*prev = NULL;
        vector<int> res;
        while(cur){
            if(!cur->left){
                res.push_back(cur->val);
                cur = cur->right;
            }else{
                prev = cur->left;
                while(prev->right && prev->right!=cur)
                    prev = prev->right;
                    
                if(!prev->right){
                    prev->right = cur;
                    res.push_back(cur->val);
                    cur = cur->left;
                }else{
                    prev->right = NULL;
                    cur = cur->right;
                }    
            }
        }
        return res;        
    }

Inorder

    vector<int> inorderTraversal(TreeNode *root) {
        // write your code here
        TreeNode *cur = root,*prev = NULL;
        vector<int> res;
        while(cur){
            if(!cur->left){
                res.push_back(cur->val);
                cur = cur->right;
            }else{
                prev = cur->left;
                while(prev->right && prev->right!=cur)
                    prev = prev->right;
                    
                if(!prev->right){
                    prev->right = cur;
                    cur = cur->left;
                }else{
                    prev->right = NULL;
                    res.push_back(cur->val);
                    cur = cur->right;
                }    
            }
        }
        return res;
    }

Postorder

void reverse(TreeNode *from, TreeNode *to) // reverse the tree nodes 'from' -> 'to'.
{
    if (from == to)
        return;
    TreeNode *x = from, *y = from->right, *z;
    while (true)
    {
        z = y->right;
        y->right = x;
        x = y;
        y = z;
        if (x == to)
            break;
    }
}

void printReverse(TreeNode* from, TreeNode *to) // print the reversed tree nodes 'from' -> 'to'.
{
    reverse(from, to);
    
    TreeNode *p = to;
    while (true)
    {
        printf("%d ", p->val);
        if (p == from)
            break;
        p = p->right;
    }
    
    reverse(to, from);
}

void postorderMorrisTraversal(TreeNode *root) {
    TreeNode dump(0);
    dump.left = root;
    TreeNode *cur = &dump, *prev = NULL;
    while (cur)
    {
        if (cur->left == NULL)
        {
            cur = cur->right;
        }
        else
        {
            prev = cur->left;
            while (prev->right != NULL && prev->right != cur)
                prev = prev->right;

            if (prev->right == NULL)
            {
                prev->right = cur;
                cur = cur->left;
            }
            else
            {
                printReverse(cur->left, prev);  // call print
                prev->right = NULL;
                cur = cur->right;
            }
        }
    }
}