C++

1class Solution {
2  public:
3    vector<int> answer;
4    vector<int> preorderTraversal(TreeNode* root) {
5      preorder(root);
6      return answer;
7    }
8
9    void preorder(TreeNode *node) {
10      if(!node) return;
11
12      answer.push_back(node->val);
13      preorder(node->left);
14      preorder(node->right);
15    }
16};

C++: Morris Traversal

1class Solution {
2void morrisTraversal(TreeNode* root) {
3  vector<int> answer;
4
5  while(root != nullptr) {
6    if(root->left == nullptr) {
7      answer.push_back(root->val);
8      root = root->right;
9    } else {
10      // inorder predecessor
11      TreeNode *curr = root->left;
12      while(curr->right && curr->right != root) curr = curr->right;
13
14      // check if inorder prede's right child is root
15      if(curr->right == root) {
16        curr->right = nullptr;
17        root = root->right;
18      } else {
19        // if not, update the right child
20        answer.push_back(root->val);
21        curr->right = root;
22        root = root->left;
23      }
24    }
25  }
26  return answer;
27}