解题思路

• 依次实现前序、中序、后序遍历；
• 将三者遍历的结果按顺序存入到结果vector中。

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    vector<int> pre, in, post;
    void preOrders(TreeNode* root) {
        if(!root)
        {
            return;
        }

        pre.push_back(root->val);
        preOrders(root->left);
        preOrders(root->right);  
    }

    void inOrders(TreeNode* root) {
        if(!root)
        {
            return;
        }

        inOrders(root->left);
        in.push_back(root->val);
        inOrders(root->right);
    }

    void postOrders(TreeNode* root) {
        if(!root)
        {
            return;
        }

        postOrders(root->left);
        postOrders(root->right);
        post.push_back(root->val);
    }
    vector<vector<int> > threeOrders(TreeNode* root) {
        vector<vector<int> >  res;
        preOrders(root);
        inOrders(root);
        postOrders(root);
        res.push_back(pre);
        res.push_back(in);
        res.push_back(post);

        return res;
    }
};

复杂度分析

• 时间复杂度为O（N）；
• 空间复杂度为O（N）。