题解 | #实现二叉树先序，中序和后序遍历#

一.题意整理

NC45实现二叉树先序，中序和后序遍历

分别按照二叉树先序遍历、中序遍历和后序遍历打印所有的节点。

二.思路整理

以先序遍历来解释，首先我们需要了解什么是二叉树的先序遍历：按照访问根节点-左子树-右子树的方式遍历这棵树，而在访问左子树和右子树的时候我们按照同样的方式遍历，直到遍历整棵树。我们对先序遍历进行进一步分析：

/*
若二叉树是空树，则什么都不做；否则：
(1)访问根节点
(2)先序遍历左子树
(3)先序遍历右子树
*/
void preorder(TreeNode* t){
        if(t!=NULL) return ;
        visit(t);//假设访问函数visit已经访问过来，其中包含看对结点t的各种操作，如打印td
        preorder(t->left);//先序遍历左子树
        preorder(t->right);//先序遍历右子树
}

后序、中序遍历实现和先序遍历实现大致相同，后序遍历是按照左子树-右子树-根节点遍历，而中序遍历是先左子树-根节点-右子树的方式遍历，所以总结来说：三种遍历方式都可以通过递归来实现。

三.代码实现

class Solution {
public:
    //先序遍历
    void preorder(TreeNode* t,vector<int> &ans){//注意这块是& 不然ans的内容无法带回去
        if(!t) return ;
        ans.push_back(t->val);
        preorder(t->left, ans);
        preorder(t->right,ans);
    }
    //中序遍历
    void inorder(TreeNode* t,vector<int> &ans){
        if(!t) return ;
        inorder(t->left, ans);
        ans.push_back(t->val);
        inorder(t->right,ans);
    }
    //后序遍历
    void postorder(TreeNode* t,vector<int> &ans){
        if(!t) return ;
        postorder(t->left, ans);
        postorder(t->right,ans);
        ans.push_back(t->val);
    }
    vector<vector<int> > threeOrders(TreeNode* root) {
        vector<vector<int>> tree;
        vector<int>q;
        preorder(root,q);//先序
        tree.push_back(q);
        q.clear();//每一次都要将q清空
        inorder(root,q);//中序
        tree.push_back(q);
        q.clear();
        postorder(root,q);//后序
        tree.push_back(q);
        q.clear();
        return tree;
    }
};

时间复杂度：$O(n)O(n)$

空间复杂度：$O(n)O(n)$需要额外开辟空间来存储结果