3ms C++ iterative solution


  • 0
    4
    class Solution
    {
    public:
        vector< int > inorderTraversal( TreeNode *root )
        {
            vector< int > out;
            stack< pair< int, TreeNode * > > toDo;
            TreeNode * current = root;
            
            for ( ;; )
            {
                if( current )
                {
                    if( current->left )
                    {
                        pair< int, TreeNode * > temp;
                        temp.first  = current->val;
                        temp.second = current->right;
                        toDo.push( temp );
                        current = current->left;
                    }
                    else
                    {
                        out.push_back( current->val );
                        if( current->right )
                        {
                            current = current->right;
                        }
                        else current = 0;
                    }
                }
                else
                {
                    if( toDo.size() )
                    {
                        out.push_back( toDo.top().first );
                        current = toDo.top().second;
                        toDo.pop();
                    }
                    else break;
                }
            }
            return out;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.