Very readable solution using stacks in C++ O(n) space and time


#1
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
void preorder(TreeNode* root, vector<int>& answer)
{
    if(root == NULL) return;
    stack<TreeNode*> S;
    S.push(root);
    while(!S.empty())
    {
        TreeNode* current = S.top();
        S.pop();
        answer.push_back(current->val);
        if(current->right != NULL) S.push(current->right);
        if(current->left != NULL) S.push(current->left);
    }
}
vector<int> Solution::preorderTraversal(TreeNode* A) 
{
    vector<int> answer;
    if(A == NULL) return answer;
    preorder(A, answer);
    return answer;
}