🔥前言
本专栏收录的均为牛客网的算法题目，内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目，也有大厂的面试真题，面试、找工作完全可以来这里找机会。此外，网站内的编码主题多样化，调试功能可运用性强，可谓是非常注重用户体验。这么好的免费刷题网站还不快入手吗，快去注册开启算法百炼成神之路吧！
1、AB16 实现二叉树先序，中序和后序遍历
使用 递归 实现，入门的难度，可以花少点时间挑战一下
题目链接：前中后序遍历
1.1、解题思路
从示例中的返回值可以看出，题目要求最终返回一个 二维数组，那么就利用灵活的 vector 容器来解题：
先使用递归法写好三个序列的遍历序列
然后用三个一维 vector容器分别存放前、中、后的遍历序列
最后将三个一维容器插进一个二维 vector 容器中并返回
1.2、代码实现及注释
本题源码：
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 the root of binary tree * @return int整型vector<vector<>> */ vector<vector<int> > res; // 二维动态数组 res vector<int> preorder, inorder, postorder; // 存放三个序列的一维数组 vector<vector<int> > threeOrders(TreeNode* root) { preOrder(root); inOrder(root); postOrder(root); // 插入二维数组中 res.push_back(preorder); res.push_back(inorder); res.push_back(postorder); return res; } // 先序遍历 void preOrder(TreeNode* root) { if (!root) return; preorder.push_back(root->val); preOrder(root->left); // 访问左子树 preOrder(root->right); // 访问右子树 } // 中序遍历 void inOrder(TreeNode* root) { if (!root) return; inOrder(root->left); // 访问左子树 inorder.push_back(root->val); inOrder(root->right); // 访问右子树 } // 后序遍历 void postOrder(TreeNode* root) { if (!root) return; postOrder(root->left); // 访问左子树 postOrder(root->right); // 访问右子树 postorder.push_back(root->val); } };
重要注释：
先、中、后序遍历的区别乍一看就是访问结点的顺序不同，但是如果去分析递归你会发现：
先序遍历：访问到一个结点后，先将值插入数组，然后往左右子树递归，不为空就插入数据，为空就停止递归。
中序遍历：一直往根结点的左子树递推，最先插入数据的一定是二叉树最左的一个结点，然后是根结点、右结点。
后序遍历：与中序类似，区别是插入最左边结点后，先处理右子树在处理根结点。
先序最好理解，像是一步步的顺序进行；而中序和后序都要先递推到最左的子树然后再回溯。
