/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */

    vector<int> a; // 存储前序遍历结果
    vector<int> b; // 存储中序遍历结果
    vector<int> c; // 存储后序遍历结果

    // 前序遍历
    void qian(TreeNode* root) {
        if (root == nullptr) return; // 如果当前节点为空,返回
        a.push_back(root->val); // 访问当前节点
        if (root->left != nullptr) {
            qian(root->left); // 递归访问左子树
        }
        if (root->right != nullptr) {
            qian(root->right); // 递归访问右子树
        }
        return;
    }

    // 中序遍历
    void zhong(TreeNode* root) {
        if (root == nullptr) return; // 如果当前节点为空,返回
        if (root->left != nullptr) {
            zhong(root->left); // 递归访问左子树
        }
        b.push_back(root->val); // 访问当前节点
        if (root->right != nullptr) {
            zhong(root->right); // 递归访问右子树
        }
        return;
    }

    // 后序遍历
    void hou(TreeNode* root) {
        if (root == nullptr) return; // 如果当前节点为空,返回
        if (root->left != nullptr) {
            hou(root->left); // 递归访问左子树
        }
        if (root->right != nullptr) {
            hou(root->right); // 递归访问右子树
        }
        c.push_back(root->val); // 访问当前节点
        return;
    }

    // 返回三种遍历结果
    vector<vector<int>> threeOrders(TreeNode* root) {
        vector<vector<int>> ans; // 存储最终结果
        qian(root); // 前序遍历
        zhong(root); // 中序遍历
        hou(root); // 后序遍历
        ans.push_back(a); // 将前序遍历结果添加到结果中
        ans.push_back(b); // 将中序遍历结果添加到结果中
        ans.push_back(c); // 将后序遍历结果添加到结果中
        return ans; // 返回结果
    }
};