【牛客题霸题解】实现二叉树先序，中序和后序遍历（待更新）

首先，我们要知道二叉树的先序、中序、后序遍历是怎么进行的，这里的先、中、后其实指的是根的位置。
举个例子来看一下

先序：根左右
{1,13,45,6,4,5,8,7,12}
中序：左根右
{45,13,4,6,1,8,7,8,12}
后序：左右根
{45,4,6,13,7,8,12,5,1}

递归写法
c++

class Solution {
public:
    //递归遍历
     void preOrder(vector<int> &ans,TreeNode* root)
     {
         if(root==NULL){return;}
         ans.push_back(root->val);
         preOrder(ans,root->left);
         preOrder(ans,root->right);
     }
     void inOrder(vector<int> &ans,TreeNode* root)
     {
         if(root==NULL){return;}
         inOrder(ans,root->left);
         ans.push_back(root->val);
         inOrder(ans,root->right);
     }
     void postOrder(vector<int> &ans,TreeNode* root)
     {
         if(root==NULL){return;}
         postOrder(ans,root->left);
         postOrder(ans,root->right);
         ans.push_back(root->val);
     }
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        vector<vector<int> > ans(3);
        preOrder(ans[0],root);
        inOrder(ans[1],root);
        postOrder(ans[2],root);
        return ans;
    }
};

java

python

非递归解法
c++

class Solution {
public:
    void PreOrder(TreeNode*root,vector<int>& ans)
    {
        stack<TreeNode*> S;
        S.push(root);
        while(!S.empty())
        {
            TreeNode* now = S.top();
            S.pop();
            if(now==NULL){continue;}
            ans.push_back(now->val);
            S.push(now->right);
            S.push(now->left);
        }
    }
    void InOrder(TreeNode*root,vector<int>& ans)
    {
        stack<TreeNode*> S;
        TreeNode* now = root;
        while(now!=NULL||!S.empty())
        { 
            if(now!=NULL)
            {
                S.push(now);
                while(now->left != NULL)
                {
                    S.push(now->left);
                    now = now->left;
                }
            }
            now = S.top();
            ans.push_back(now->val);
            S.pop();
            now = now->right;
        }
    }
    void PostOrder(TreeNode*root,vector<int>& ans)
    {
        stack< pair<TreeNode*,int> > S;
        S.push( pair<TreeNode*,int>(root,0) );
        while(!S.empty())
        {
            TreeNode* now = S.top().first;
            if(S.top().second == 0)
            {
                S.top().second = 1;
                while(now->left != NULL)
                {
                    S.push( pair<TreeNode*,int>(now->left,1));
                    now = now->left;
                }
            }
            TreeNode* Top = S.top().first;
            int visit = S.top().second;
            if(visit==2 || Top->right==NULL)
            {
                ans.push_back(Top->val);
                S.pop();
            }
            else {
                S.top().second++;
                S.push( pair<TreeNode*,int>(Top->right,0));
            }
        }
    }
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        vector<vector<int> > ans(3);
        PreOrder(root, ans[0]);
        InOrder(root, ans[1]);
        PostOrder(root, ans[2]);
        return ans;
    }
};