The recursive solution is trivial and I omit it here.

Iterative Solution using Stack (O(n) time and O(n) space):

1 /** 2  * Definition of TreeNode: 3  * class TreeNode { 4  * public: 5  *     int val; 6  *     TreeNode *left, *right; 7  *     TreeNode(int val) { 8  *         this->val = val; 9  *         this->left = this->right = NULL;10  *     }11  * }12  */13 14 class Solution {15 public:16     /**17      * @param root: The root of binary tree.18      * @return: Preorder in vector which contains node values.19      */20     vector
     
       preorderTraversal(TreeNode *root) {21         // write your code here22         vector
      
        nodes;23         TreeNode* node = root;24         stack
       
         right;25         while (node || !right.empty()) {26             if (node) {27                 nodes.push_back(node -> val);28                 if (node -> right)29                     right.push(node -> right);30                 node = node -> left;31             }32             else {33                 node = right.top();34                 right.pop();35             }36         }37         return nodes;38     }39 };
       
      
     

Another more sophisticated solution using Morris Traversal (O(n) time and O(1) space):

1 /** 2  * Definition of TreeNode: 3  * class TreeNode { 4  * public: 5  *     int val; 6  *     TreeNode *left, *right; 7  *     TreeNode(int val) { 8  *         this->val = val; 9  *         this->left = this->right = NULL;10  *     }11  * }12  */13 14 class Solution {15 public:16     /**17      * @param root: The root of binary tree.18      * @return: Preorder in vector which contains node values.19      */20     vector
     
       preorderTraversal(TreeNode *root) {21         // write your code here22         vector
      
        nodes;23         TreeNode* node = root;24         while (node) {25             if (node -> left) {26                 TreeNode* predecessor = node -> left;27                 while (predecessor -> right && predecessor -> right != node)28                     predecessor = predecessor -> right;29                 if (!(predecessor -> right)) {30                     nodes.push_back(node -> val);31                     predecessor -> right = node;32                     node = node -> left;33                 }34                 else {35                     predecessor -> right = NULL;36                     node = node -> right;37                 }38             }39             else {40                 nodes.push_back(node -> val);41                 node = node -> right;42             }43         }44         return nodes;45     }46 };