递归版本

class Solution {
public:
    vector<int> res;
    vector<int> preorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }

    // 前序
    void dfs(TreeNode* root){
        if(!root) return;
        res.push_back(root->val);
        dfs(root->left);
        dfs(root->right);
    }

   // 中序
    void dfs(TreeNode* root){
        if(!root) return;
        dfs(root->left);
        res.push_back(root->val);
        dfs(root->right);
    }

    // 后序
    void dfs(TreeNode* root){
        if(!root) return;
        dfs(root->left);
        dfs(root->right);
        res.push_back(root->val);
    }
};

递归容易，遍历不好理解。这里总结下，前中后类似，后序多一个prev表示之前遍历过的节点

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// 前序
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root || stk.size()) {
            while (root) {
                res.push_back(root->val);  //前序在进栈前add value
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();

            root = root->right;
        }
        return res;
    }
};

//中序
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while(root || stk.size()){
            while(root) {
                stk.push(root);
                root = root -> left;
            }
            root = stk.top();
            stk.pop();

            res.push_back(root->val); //中序出栈后，add value
            root = root->right;
        }
        return res;
    }
};

//后序
class Solution {
public:
    vector<int> res;
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        stack<TreeNode*> stk;
        TreeNode* prev = nullptr;//后序遍历需要额外的 prev指针，表示上次加入res的节点
        while(root || stk.size()){
            while(root) {
                stk.push(root);
                root = root -> left;
            }
            root = stk.top();
            stk.pop();

            //root不存在右节点，或者，root右节点上次已经遍历了(prev代表上次已add)
            if(!root->right||root->right == prev){
                res.push_back(root->val);
                prev = root;
                root = nullptr;
            } else { // 存在右节点，且还未被遍历，则先入栈
                stk.push(root);
                root = root->right;
            }
        }
        return res;
    }
};