Simple O(n) solution using stack and queue

[ankit-sharma_381]

vector<int> Solution::solve(TreeNode* A)
{
    queue<TreeNode*> q;
    stack<int> s;
    q.push(A);
    while(!q.empty())
    {
        int size = q.size();
        for(int i=0; i<size; i++)
        {
            s.push(q.front()->val);
            if(q.front()->right) q.push(q.front()->right); //pushing the right first so that it goes in the stack first and comes out later
            if(q.front()->left) q.push(q.front()->left);
            q.pop();
        }
    }
    vector<int> res;
    while(!s.empty())
    {
        res.push_back(s.top());
        s.pop();
    }
    return res;
}