4 solutions in c++
\n    // recursive, but it's trivial...\n    vector preorderTraversal(TreeNode root) {\n        vector v;\n        preTraversal(root, v);\n        return v;\n  
\n    // recursive, but it's trivial...\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> v;\n        preTraversal(root, v);\n        return v;\n    }\n    void preTraversal(TreeNode* root, vector<int>& v){\n        if(!root) return;\n        v.push_back(root->val);\n        preTraversal(root->left, v);\n        preTraversal(root->right, v);\n    }\n    \n    \n    // iterate, use stack to imitate recursive\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> v;\n        if(!root) return v;\n        TreeNode* temp = root;\n        stack<TreeNode*> s;\n        s.push(root);\n        while(!s.empty()){\n            temp = s.top();\n            s.pop();\n            v.push_back(temp->val);\n            if(temp->right) s.push(temp->right);\n            if(temp->left) s.push(temp->left);\n        }\n    }\n    \n    \n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> v;\n        if(!root) return v;\n        TreeNode* temp = root;\n        stack<TreeNode*> s;\n        while(true){\n            while(temp){\n                v.push_back(temp->val);\n                if(temp->right) s.push(temp->right);\n                temp = temp->left;\n            }\n            if(s.empty()) break;\n            temp = s.top();\n            s.pop();\n        };\n    }\n    \n    // morris traversal\uff0c O(1) space\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> v;\n        if(!root) return v;\n        TreeNode* temp = root, *prev;\n        while(temp){\n            if(!temp->left){\n                v.push_back(temp->val);\n                temp = temp->right;\n            }else{\n                prev = temp->left;\n                while(prev->right&&(prev->right != temp))\n                    prev = prev->right;\n                if(!prev->right){\n                    v.push_back(temp->val);\n                    prev->right = temp;\n                    temp = temp->left;\n                }else{\n                    prev->right = NULL;\n                    temp = temp->right;\n                }\n            }\n        }\n    }
['C++']