二叉树非递归前中后遍历

前序：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*>stk;
        auto cur = root;
        vector<int>res;
        while(cur || stk.size()) {
            while(cur){
                stk.push(cur);
                res.push_back(cur->val);
                cur = cur->left;
            }
            cur = stk.top();
            stk.pop();
            cur = cur->right;
        }
        return res;
    }
};

中序：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*>stk;
        vector<int>res;
        auto cur = root;
        while(cur || stk.size()){
            while(cur){
                stk.push(cur);
                cur=cur->left;
            }
            cur = stk.top();
            stk.pop();
            res.push_back(cur->val);
            cur = cur->right;
        }
        return res;
    }
};

后序：
该代码是基于前序遍历改来的，由于前序遍历是中左右，后序遍历是左右中，所以只需要写出中右左，再进行反转即可得到左右中。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*>stk;
        auto cur = root;
        vector<int>res;
        while(cur || stk.size()) {
            while(cur){
                stk.push(cur);
                res.push_back(cur->val);
                cur = cur->right;
            }
            cur = stk.top();
            stk.pop();
            cur = cur->left;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};