C++ Easy Solution Using Recursion and Moris traversal
C++ Easy Solution Using Recursion and Moris traversal\n # Recursive Traversal\n\nclass Solution {\npublic:\n    void preorder(TreeNode*&root,vector<int>&pre){\n
# **C++ Easy Solution Using Recursion and Moris traversal**\n* # **Recursive Traversal**\n```\nclass Solution {\npublic:\n    void preorder(TreeNode*&root,vector<int>&pre){\n        if(root){\n            pre.push_back(root->val);\n            preorder(root->left,pre);\n            preorder(root->right,pre);\n        }\n    }\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> pre;\n        preorder(root,pre);\n        return pre;\n    }\n};\n```\n# ***Time Complexity : `O(N)`***\n# ***Space Complexity : `O(N)`***\n* # **Moris Traversal**\n```\nclass Solution {\npublic:\n    TreeNode* rightMostFinder(TreeNode*cur,TreeNode*root){\n        while(cur->right&&cur->right!=root){\n            cur=cur->right;\n        }\n        return cur;\n    }\n    vector<int> preorderTraversal(TreeNode* root) {\n        TreeNode*cur=root;\n        vector<int>ans;\n        while(cur){\n            TreeNode*leftNode=cur->left;\n            if(leftNode){\n                TreeNode*RightMost=rightMostFinder(leftNode,cur);\n                if(RightMost->right){\n                    RightMost->right=nullptr;\n                    cur=cur->right;\n                }\n                else{\n                    RightMost->right=cur;\n                    ans.push_back(cur->val);\n                    cur=cur->left;\n                }\n            }\n            else{\n                ans.push_back(cur->val);\n                cur=cur->right;\n            }\n        }\n        return ans;\n    }\n};\n```\n# ***Time Complexity : `O(N)`***\n# ***Space Complexity : `O(1)`***\n# **Please Upvote if solution Helped You It really motivates me\uD83D\uDE0A**\n
['Recursion', 'C', 'Binary Tree', 'C++']