二叉法的前中后序的遍历， 前中后所说的是根节点输出的顺序；
有两种遍历方式，
1. 递归法 （自己调用自己，本质是用栈）
代码比较简单，但是需要创建一个额外的函数来进行自己调用自己的过程；用递归法的话三种遍历方式只需要改变代码的位置就可以。
Leetcode 对应的三道题和代码如下；
- 144.二叉树的前序遍历(opens new window)
- 145.二叉树的后序遍历(opens new window)
-
94.二叉树的中序遍历
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void get_result(TreeNode* root,vector<int>&result){ if( root == NULL) return ; result.push_back(root->val); get_result(root->left,result); get_result(root->right,result); } vector<int> preorderTraversal(TreeNode* root) { vector<int> result; get_result(root,result); return result; } };2.迭代法
-
迭代法就比较复杂，本质上是自己用stack来实现递归的过程。而且要注意迭代法的前序 和 中序的逻辑不一样，所以不能简单的改代码位置就把前序改成中序；后序就是搭了前序的顺风车把自己的结果reverse了一下；中序还是比较难写而且只看代码看不太懂，要结合视频看；
具体区别如下：
分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。因为你拿到一个数肯定第一个访问的是root节点；
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。文章来源：https://www.toymoban.com/news/detail-476343.html
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。文章来源地址https://www.toymoban.com/news/detail-476343.html
到了这里，关于代码随想录刷题 Day14的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
