[二叉树专题]前中后递归遍历和非递归遍历

一、先序遍历

class Solution {
public:
void pre(TreeNode* root,vector<int>&p)
{
if(root!=nullptr)
{
    p.push_back(root->val);
    pre(root->left,p);
    pre(root->right,p);
}
}
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> p;
        pre(root,p);
        return p;
    }
};

二、先序非递归

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> p;
        vector<int> result;
        if (root != nullptr) {
            p.push(root);
        }
        while (!p.empty()) {
            TreeNode*q=p.top();
            p.pop();
            result.push_back(q->val);
            if (q->right!=nullptr)
                p.push(q->right);
            if (q->left!=nullptr)
                p.push(q->left);
        }
        return result;
    }
};

?二、中序非递归

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> p;
        if (root == nullptr)
            return result;
        TreeNode* s = root;
        while (s != nullptr || !p.empty()) {
            if (s != nullptr) {
                p.push(s);
                s = s->left;
            } else {
                s = p.top();
                p.pop();
                result.push_back(s->val);
                s = s->right;
            }
        }
        return result;
    }
};

三、后序非递归:前序中左右子树入栈顺序稍作修改，将最后结果反转即可达到后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
     vector<int>result;
     stack<TreeNode*>p;
     TreeNode*q;
     if(root==nullptr)
     return  result;
     p.push(root);
     while(!p.empty())
     {
       q=p.top();
       result.push_back(q->val);
       p.pop();
       if(q->left)p.push(q->left);
       if(q->right)p.push(q->right);
     }
     reverse(result.begin(),result.end());
     return result;
    }
};