1/*Morris traversal */
2class Solution {
3  public:
4    vector<int> inorderTraversal(TreeNode* root) {
5      vector<int> answer;
6
7      while(root != nullptr) {
8        if(root->left == nullptr) {
9          answer.push_back(root->val);
10          root = root->right;
11        } else {
12          TreeNode *curr = root->left;
13          while(curr->right && curr->right != root) curr = curr->right;
14
15          if(curr->right == nullptr) {
16            curr->right = root;
17            root = root->left;
18          } else {
19            // if not, update the right child
20            curr->right = nullptr;
21            answer.push_back(root->val);
22            root = root->right;
23          }
24        }
25      }
26
27      return answer;
28    }
29};