Morris Traversal for Preorder/Inorder/Postorder

Morris Traversal for tree traversal. Time complexity O(n), Space complexity O(1)
Data structure definition.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

Preorder

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        auto p = root;
        while (p) {
            if (!p->left) {
                ans.emplace_back(p->val);
                p = p->right;
            } else {
                auto prev = p->left;
                while (prev->right and prev->right != p) {
                    prev = prev->right;
                }
                if (!prev->right) {
                    ans.emplace_back(p->val);
                    prev->right = p;
                    p = p->left;
                } else {
                    prev->right = nullptr;
                    p = p->right;
                }
            }
        }
        return ans;
    }
};

Inorder (The difference between Inorder and Preorder is only one line)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        auto p = root;
        while (p) {
            if (!p->left) {
                ans.emplace_back(p->val);
                p = p->right;
            } else {
                auto prev = p->left;
                while (prev->right and prev->right != p) {
                    prev = prev->right;
                }
                if (!prev->right) {
                    prev->right = p;
                    p = p->left;
                } else {
                    ans.emplace_back(p->val);   \\ diff
                    prev->right = nullptr;
                    p = p->right;
                }
            }
        }
        return ans;
    }
};

Postorder (The visiting order is a mirror reflection of Preorder, and the results should be reversed)

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        auto p = root;
        while (p) {
            if (!p->right) {
                ans.insert(ans.begin(), p->val);
                p = p->left;
            } else {
                auto post = p->right;
                while (post->left and post->left != p) {
                    post = post->left;
                }
                if (!post->left) {
                    ans.insert(ans.begin(), p->val);
                    post->left = p;
                    p = p->right;
                } else {
                    post->left = nullptr;
                    p = p->left;
                }
            }
        }
        return ans;
    }
};