Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1

2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?

Solution: 1. Iterative way (stack). Time: O(n), Space: O(n).
2. Recursive solution. Time: O(n), Space: O(n).
3. Threaded tree (Morris). Time: O(n), Space: O(1).

 1 class Solution {
 2 public:
 3     vector<int> inorderTraversal(TreeNode *root) {
 4         return inorderTraversal_1(root);
 5     }
 6     
 7     vector<int> inorderTraversal_1(TreeNode *root) {
 8         vector<int> res;
 9         stack<TreeNode *> stk;
10         TreeNode *cur = root;
11         while (cur || !stk.empty())
12         {
13             if (cur)
14             {
15                 stk.push(cur);
16                 cur = cur->left;
17             }
18             else if (!stk.empty())
19             {
20                 res.push_back(stk.top()->val);
21                 cur = stk.top()->right;
22                 stk.pop();
23             }
24         }
25         return res;
26     }
27     
28     vector<int> inorderTraversal_2(TreeNode *root) {
29         vector<int> res;
30         inorderTraversalRe(root, res);
31         return res;
32     }
33 
34     void inorderTraversalRe(TreeNode *node, vector<int> &res) {
35         if (!node) return;
36         inorderTraversalRe(node->left, res);
37         res.push_back(node->val);
38         inorderTraversalRe(node->right, res);
39     }
40     
41     vector<int> inorderTraversal_3(TreeNode *root) {
42         vector<int> res;
43         TreeNode *cur = root;
44         while (cur)
45         {
46             if (cur->left)
47             {
48                 TreeNode *prev = cur->left;
49                 while (prev->right && prev->right != cur)
50                     prev = prev->right;
51                     
52                 if (prev->right == cur)
53                 {
54                     res.push_back(cur->val);
55                     cur = cur->right;
56                     prev->right = NULL;
57                 }
58                 else
59                 {
60                     prev->right = cur;
61                     cur = cur->left;
62                 }
63             }
64             else
65             {
66                 res.push_back(cur->val);
67                 cur = cur->right;
68             }
69         }
70         return res;
71     }
72 };