常规解法
先来一个最容易理解的版本
/** * 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; } };
递归层数减少,理论处理时间少于第一个方案。但时间复杂度无变化。