Binary Tree Iterative Traversal

Preorder

 1 class Solution {
 2 public:
 3     vector<int> preorderTraversal(TreeNode* root) {
 4         vector<int> res;
 5         if (!root) return res;
 6         stack<TreeNode *> sta;
 7         sta.push(root);
 8         while (!sta.empty())
 9         {
10             TreeNode* cur = sta.top();
11             sta.pop();
12             res.push_back(cur->val);
13             if (cur->right) sta.push(cur->right);
14             if (cur->left) sta.push(cur->left);
15         }
16         return res;
17     }
18 };

postorder

 1 class Solution {
 2 public:
 3     vector<int> postorderTraversal(TreeNode* root) {
 4         vector<int> res;
 5         if (!root) return res;
 6         stack<TreeNode *> sta;
 7         sta.push(root);
 8         TreeNode *last = NULL;
 9         while (!sta.empty())
10         {
11             TreeNode *cur = sta.top();
12             TreeNode *left = cur->left, *right = cur->right;
13             if (left && (!last || (last != left && last != right)))
14                 sta.push(left);
15             else if (right && (!last || last != right))
16                 sta.push(right);
17             else
18             {
19                 res.push_back(cur->val);
20                 last = cur;
21                 sta.pop();
22             }
23         }
24         return res;
25     }
26 };

inorder

 1 class Solution {
 2 public:
 3     vector<int> inorderTraversal(TreeNode* root) {
 4         vector<int> res;
 5         stack<TreeNode*> sta;
 6         while(1) {
 7             while(root) { sta.push(root); root = root->left; }
 8             if(sta.empty()) break;
 9             root = sta.top(); sta.pop();
10             res.push_back(root->val);
11             root = root->right;
12         }
13         return res;
14     }
15 };