#include "leetcode.h"

class Solution {
public:
  vector<int> preorderTraversal(TreeNode *root) {
    // morris traversal
    vector<int> nodes;
    while (root) {
      if (root->left) {
        TreeNode *pre = root->left;
        while (pre->right && pre->right != root)
          pre = pre->right;
        if (!pre->right) {
          pre->right = root;
          nodes.push_back(root->val);
          root = root->left;
        } else {
          pre->right = NULL;
          root = root->right;
        }
      } else {
        nodes.push_back(root->val);
        root = root->right;
      }
    }
    return nodes;
  }
};