题目：

前：

中：

后：

---

代码（首刷自解 2024年1月24日）：

//前序遍历，递归
class Solution {
public:
    void funcOfRecursion(TreeNode* cur, vector<int>& vec) {
        if (cur == nullptr) return;
        vec.emplace_back(cur->val);
        funcOfRecursion(cur->left,vec);
        funcOfRecursion(cur->right,vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> vec = {};
        if (root == nullptr) return vec;
        funcOfRecursion(root,vec);
        return vec; 
    }
};

//中序遍历，递归
class Solution {
public:
    void funcOfRecursion(TreeNode* cur,vector<int>& vec) {
        if(cur == nullptr) return;
        funcOfRecursion(cur->left,vec);
        vec.emplace_back(cur->val);
        funcOfRecursion(cur->right,vec);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> vec = {};
        if(root == nullptr) return vec;
        funcOfRecursion(root,vec);
        return vec;
    }
};

//后序遍历，递归
class Solution {
public:
    void funcOfRecursion(TreeNode* cur, vector<int>& vec) {
        if(cur == nullptr) return;
        funcOfRecursion(cur->left,vec);
        funcOfRecursion(cur->right,vec);
        vec.emplace_back(cur->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> vec = {};
        if(root == nullptr) return vec;
        funcOfRecursion(root,vec);
        return vec;
    }
};

//前序遍历，迭代
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res = {};
        if(root == nullptr) return res;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        st.push(cur);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            res.emplace_back(node->val);
            if(node->right) st.push(node->right);
            if(node->left) st.push(node->left);
        }
        return res;
    }
};

//中序遍历，迭代
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res = {};
        if(root == nullptr) return res;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (!st.empty() || cur != NULL) {
            if (cur != nullptr) {
                st.push(cur);
                cur = cur -> left;
            } else {
                cur = st.top();
                res.emplace_back(cur->val);
                st.pop();
                cur = cur -> right;
            }
        }
        return res;
    }
};

//后序遍历 迭代
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res = {};
        if(root == nullptr) return res;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        st.push(cur);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            res.emplace_back(node->val);
            if(node->left) st.push(node->left);
            if(node->right) st.push(node->right);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

代码（二刷自解 2024年1月24日  morris遍历）：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res = {};
        if(root == nullptr) return res;
        TreeNode* cur = root;
        while (cur != nullptr) {
            if (cur->left) {
                TreeNode* predessor = cur->left;
                while (predessor->right && predessor->right != cur) {
                    predessor = predessor->right;
                }
                if (predessor->right == cur) {
                    predessor->right = nullptr;
                    cur = cur->right;
                } else {
                    res.emplace_back(cur->val);
                    predessor->right = cur;
                    cur = cur->left;
                }
            } else {
                res.emplace_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

        morris前序遍历，时间复杂度O(n），空间复杂度O(1)；

设当前节点为cur

while (cur!=nullptr) {

        if(cur有左孩子）{

                if(cur的前驱右孩子是x) 前驱右孩子设为null，cur = cur右孩子；

                if(cur的前驱右孩子为空) cur加入结果数组，前驱右孩子设为cur，cur=cur左孩子；

        }

        else if(cur没有左孩子){

                cur加入结果数组；

                cur = cur ->right;

        }

}