手撕二叉树 非递归 前序中序后序遍历

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int val):val(val),left(nullptr),right(nullptr){}
};

//非递归的前序遍历
vector<int> preorder(TreeNode* root){
    vector<int> ans;
    if (root == NULL)
        return ans;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* cur = s.top();
        s.pop();
        ans.push_back(cur->val);
        if (cur->left)
            s.push(cur->left);
        if (cur->right)
            s.push(cur->right);
    }
    return ans;
}

//非递归的中序遍历
vector<int> inorder(TreeNode* root) {
    vector<int> ans;
    if (root == NULL)
        return ans;
    stack<TreeNode*> s;
    while (root != NULL || !s.empty()) {
        while (root != NULL) {
            s.push(root);
            root = root->left;
        }
        TreeNode* cur = s.top();
        s.pop();
        ans.push_back(cur->val);
        root = cur->right;
    }
    return ans;
}

//非递归的后序遍历
vector<int> postorder(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> s;
    TreeNode* pre = NULL;
    while (root != NULL || !s.empty()) {
        while (root != NULL) {
            s.push(root);
            root = root->left;
        }
        TreeNode* cur = s.top();
        s.pop();
        if (cur->right == NULL || cur->right == pre) {
            ans.push_back(cur->val);
            pre = cur;
        }
        else {
            s.push(cur);
            root = cur->right;
        }
    }
    return ans;
}