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?

思路：

要求递归实现，所以引入一个栈。又因为避免重复进入已访问的节点，所以用pair来记录某个节点是否被访问。

代码：

 1     vector<int> preorderTraversal(TreeNode *root) {
 2         // IMPORTANT: Please reset any member data you declared, as
 3         // the same Solution instance will be reused for each test case.
 4         stack<pair<TreeNode*, bool> > s;
 5         vector<int> result;
 6         if(root == NULL)
 7             return result;
 8         s.push(pair<TreeNode*, bool>(root, false));
 9         pair<TreeNode*, bool> tPair;
10         TreeNode* tNode;
11         bool hasVisited;
12         while(!s.empty()){
13             tPair = s.top();
14             tNode = tPair.first;
15             hasVisited = tPair.second;
16             if(hasVisited){
17                 s.pop();
18                 if(tNode->right != NULL)
19                     s.push(pair<TreeNode*, bool>(tNode->right, false));
20             }
21             else{
22                 s.pop();
23                 s.push(pair<TreeNode*, bool>(tNode, true));
24                 result.push_back(tNode->val);
25                 if(tNode->left != NULL)
26                     s.push(pair<TreeNode*, bool>(tNode->left, false));
27             }
28         }
29         return result;
30     }