递归版本不写了，主要归纳下个人认为比较简洁好理解的迭代做法

前序遍历

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;if(!root) return res;
    stack<TreeNode*> stk;
    TreeNode* cur = root;
    while(cur || !stk.empty()){
        while(cur){
            res.emplace_back(cur->val);
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top();
        stk.pop();
        cur = cur->right;
    }
    return res;
}

中序遍历

vector<int> inorderTraversal(TreeNode* root){
    vector<int> mid;
    stack<TreeNode*> stk; 
    auto p = root;
    while(p || stk.size())
    {
        while(p)
        {
            stk.push(p);
            p = p->left;
        }
        p = stk.top();
        mid.push_back(p->val);
        stk.pop();
        p = p->right;
    }
    return mid;
}

后序遍历

leetcode145: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        stack<TreeNode*> stk;
        TreeNode* lastvisit = nullptr; //store last visit node
        while(root || !stk.empty()){
            while(root){
                stk.push(root);
                root = root->left;
            }
            auto peek = stk.top();
            if(peek->right != nullptr && peek->right != lastvisit) {
                root = peek->right;
            }else{
                res.emplace_back(peek->val);
                stk.pop();
                lastvisit = peek;
            }
        }
        std::cout << stk.size();
        return res;
    }
};
// 例如：  1
//       2   3   

• 后序遍历的迭代算法，注意的一点是保存上次访问的节点,也可以用On空间保存所有节点的访问状态
  当peek==1的时候，右节点是存在的，要记录上一次是不是从3-1返回的，因为可能是2-1或3-1返回1，
  如果是3-1，lastvisit节点就是3，说明peek的右边已经访问过了，不能再访问，不然就是23333死循环
• 也可以 根-右-左遍历再倒转数组，注前序遍历是 根-左-右， 中序遍历是 左-根-右

 vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;if(!root) return res;
    stack<TreeNode*> stk;
    TreeNode* cur = root;
    while(cur || !stk.empty()){
        while(cur){
            res.emplace_back(cur->val);
            stk.push(cur);
            cur = cur->right;
        }
        cur = stk.top();
        stk.pop();
        cur = cur->left;
    }
    reverse(res.begin(), res.end());
    return res;
}

层序遍历

• 注意输出到二维数组还是一维数组，做法略有不同，输出到一维数组较简单，输出到二维数组有一个遍历当前层队列的过程

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if(!root) return res;
    queue<TreeNode*> que;
    que.push(root);
    vector<int> level;

    while(que.size()) {
        int len = que.size();
        for(int i = 0; i < len; i++){ //遍历当前层，输出一维数组则没有这个
            TreeNode* t = que.front();
            level.emplace_back(t->val);
            que.pop();            
            if(t->left) que.push(t->left);
            if(t->right) que.push(t->right);   
        }   
        res.emplace_back(level);            
        level.clear();     
    }
    return res;
}