Cacher is the code snippet organizer for pro developers

// Recursive solution
class Solution {
public:
    void preorder(std::vector<int>& tree, TreeNode* root) {
        if (root) {
            tree.push_back(root->val);
            preorder(tree, root->left);
            preorder(tree, root->right);
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> tree;
        preorder(tree, root);
        return tree;
    }
};

// Iterative solution
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> tree;
        std::stack<TreeNode*> roots;
        
        if (!root) return tree;
        
        roots.push(root);
        while (!roots.empty()) {
            auto top = roots.top();
            tree.push_back(top->val);
            roots.pop();
            if (top->right) roots.push(top->right);
            if (top->left) roots.push(top->left);
        }
        
        return tree;
    }
};

// Morris Traversal
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> tree;
        
        while (root) {
            if (root->left) {
                auto next = root->left;
                while (next->right && next->right != root) {
                    next = next->right;
                }
                
                if (next->right == root) {
                    next->right = nullptr;
                    root = root->right;
                } else {
                    next->right = root;
                    tree.push_back(root->val);
                    root = root->left;
                }
            } else {
                tree.push_back(root->val);
                root = root->right;
            }
        }
        
        return tree;
    }
};