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*> s;
15 TreeNode* current = root;
16
17 while(current){
18 result.push_back(current->val);
19 if(current->left && current->right) s.push(current);
20
21 if(current->left){
22 current = current->left;
23 }
24 else if(current->right){
25 current = current->right;
26 }
27 else if(!s.empty()){
28 current = s.top()->right;
29 s.pop();
30 }
31 else{
32 current = nullptr;
33 }
34 }
35
36 return result;
37 }
38 };