Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Analyse: root, root->left, root->right

1. Recursion

Runtime: 0ms

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> preorderTraversal(TreeNode *root) {
13         vector<int> result;
14         preorder(root, result);
15         return result;
16     }
17     void preorder(TreeNode* root, vector<int>& result){
18         if(root){
19             result.push_back(root->val);
20             preorder(root->left, result);
21             preorder(root->right, result);
22         }
23         return ;
24     }
25 };

2. Iteration

　 Runtime: 4ms

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> preorderTraversal(TreeNode *root) {
13         vector<int> result;
14         stack<TreeNode*> stk;
15         if(root) stk.push(root);
16         else return result;
17         
18         while(!stk.empty()){
19             TreeNode* temp = stk.top();
20             result.push_back(temp->val);
21             stk.pop();
22             
23             if(temp->right) stk.push(temp->right);
24             if(temp->left) stk.push(temp->left);
25         }
26         return result;
27     }
28 };