C++ Iterative, Recursive and Morris Traversal
There are three solutions to this problem.\n\n 1. Iterative solution using stack --- O(n) time and O(n) space;\n 2. Recursive solution --- O(n) time and O(n) sp
There are three solutions to this problem.\n\n 1. Iterative solution using stack --- `O(n)` time and `O(n)` space;\n 2. Recursive solution --- `O(n)` time and `O(n)` space (function call stack);\n 3. Morris traversal --- `O(n)` time and `O(1)` space.\n\n**Iterative solution using stack**\n\n```cpp\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> nodes;\n        stack<TreeNode*> todo;\n        while (root || !todo.empty()) {\n            if (root) {\n                nodes.push_back(root -> val);\n                if (root -> right) {\n                    todo.push(root -> right);\n                }\n                root = root -> left;\n            } else {\n                root = todo.top();\n                todo.pop();\n            }\n        }\n        return nodes;\n    }\n};\n```\n\n**Recursive solution**\n\n```cpp\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> nodes;\n        preorder(root, nodes);\n        return nodes;\n    }\nprivate:\n    void preorder(TreeNode* root, vector<int>& nodes) {\n        if (!root) {\n            return;\n        }\n        nodes.push_back(root -> val);\n        preorder(root -> left, nodes);\n        preorder(root -> right, nodes);\n    }\n};\n```\n\n**Morris traversal**\n\n```cpp\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> nodes;\n        while (root) {\n            if (root -> left) {\n                TreeNode* pre = root -> left;\n                while (pre -> right && pre -> right != root) {\n                    pre = pre -> right;\n                }\n                if (!pre -> right) {\n                    pre -> right = root;\n                    nodes.push_back(root -> val);\n                    root = root -> left;\n                } else {\n                    pre -> right = NULL;\n                    root = root -> right;\n                }\n            } else {\n                nodes.push_back(root -> val);\n                root = root -> right;\n            }\n        }\n        return nodes;\n    }\n};\n```
['Stack', 'Recursion', 'Binary Tree', 'Iterator', 'C++']