常规解法

先来一个最容易理解的版本

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
private:
    vector<int> pre;
    vector<int> in;
    vector<int> post;

private:
    // 递归是最容易的方法
    void pre_traver (const TreeNode* root) {
        // 中 左 右
        if (root != nullptr) {
            // 中
            this->pre.push_back(root->val);
            // 左
            vector<int> left = pre_traver(root->left);
            // 右
            vector<int> right = pre_traver(root->right);
        }
    }

    void in_traver (const TreeNode* root) {
        if (root != nullptr) {
            // 左
            vector<int> left = in_traver(root->left);
            // 中
            this->in.push_back(root->val);
            // 右
            vector<int> right = in_traver(root->right);
        }
    }

    void pos_traver (const TreeNode* root) {
        if (root != nullptr) {
            // 左
            vector<int> left = pos_traver(root->left);
            // 右
            vector<int> right = pos_traver(root->right);
            // 中
            this->post.push_back(root->val);
        }
    }
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */

    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        // 先序: 中 左 右
        pre_traver(root);
        // 中序: 左 中 右
        in_traver(root);
        // 后序: 左 右 中
        pos_traver(root);

        vector<vector<int>> res{this->pre, this->in, this->post};

        return res;
    }
};

代码简化版本

结合题目,我们要返回的是一个vector<vector<int>>值,而前面的代码是常规的思路,也不难发现其中的遍历有许多重复或类似的代码。

如果出现重复和类似,我们可以尝试将他们合并,但将三个方法合并成一个,好处仅仅是减少代码量和减少递归次数,不方便扩展(这估计也扩展不了啥(溜

直接贴代码:

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
private:
    vector<vector<int>> res{3};

private:
    void traver(const TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        // 先序
        res[0].push_back(root->val);
        // 中序
        traver(root->left);
        res[1].push_back(root->val);
        // 后序
        traver(root->right);
        res[2].push_back(root->val);
    }

public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */

    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        this->traver(root);
        return this->res;
    }
};

递归层数减少,理论处理时间少于第一个方案。但时间复杂度无变化。