二叉树的中序遍历（三种方法）

题目：

原题链接
简述题目就是：给你一颗二叉树的根结点root返回它的中序遍历

方法一（递归）：

中序遍历： 简单来说就是按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。口诀就是先左，再根，后右（看到这还是不明白的，可以自己查一下）

具体思路：

我们先定义root表示当前访问的结点，如果该结点为空则直接返回。如果不为空，则递归访问这个结点的左子树，然后把当前结点的值加入答案res中，然后递归访问该结点的右子树。

代码

class Solution {
public:void inorder(TreeNode* root, vector<int>& res) {if (!root)return;inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);}vector<int> inorderTraversal(TreeNode* root) {vector<int> res;inorder(root, res);return res;}
};

方法二（迭代）

具体思路：

按照上面递归是思路，我们只需要模拟出一个栈stk即可。我们还是用root来表示当前访问的结点，只要root不为空或者栈stk不为空我们就一直循环。先访问root的左孩子，只要左孩子不为空，我们就把root压入栈，并且把root=root->left，一直循环直至左孩子为空。我们再把栈顶取出并把它加入到答案中，并让root=root->right。

代码

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> stk;while (root != nullptr || !stk.empty()) {while (root != nullptr) {stk.push(root);root = root->left;}root = stk.top();stk.pop();res.push_back(root->val);root = root->right;}return res;}
};

方法三（Morris遍历）

思路：

重要变量说明
root:表示当前访问的结点
pre：表示root的左子树上最右的结点（即左子树中序遍历的最后一个结点，也可以称之为root中序遍历的前驱结点）

如果root无左孩子，那就把root加入答案数组，再令root=root->right
如果root有左孩子，那我们先找到pre,
- 如果pre为空，那我们就将pre->right=root,再令root=root->left。
- 如果pre不为空，那就说明root的左子树已经访问完了，我们把root加入答案，同时剪断链接pre->right=nullptr（因为root的左子树中最右的结点pre本来没有右孩子，我们之前临时使pre 的右孩子为root，这会打乱二叉树的结构，所以我们要还原），再令root=root->right。
一直循环直至遍历完整棵树。

代码

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;TreeNode *predecessor = nullptr;while (root != nullptr) {if (root->left != nullptr) {// predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止predecessor = root->left;while (predecessor->right != nullptr && predecessor->right != root) {predecessor = predecessor->right;}// 让 predecessor 的右指针指向 root，继续遍历左子树if (predecessor->right == nullptr) {predecessor->right = root;root = root->left;}// 说明左子树已经访问完了，我们需要断开链接else {res.push_back(root->val);predecessor->right = nullptr;root = root->right;}}// 如果没有左孩子，则直接访问右孩子else {res.push_back(root->val);root = root->right;}}return res;}
};

个人总结：

三种方法中第一中递归最好想也最好写，没什么思维难度，但是递归不安全，对于严重线性化的二叉树有可能栈溢出。第二种迭代的方法难度也不大，就是需要我们把递归中隐形的栈给手动模拟出来。难度最大的是第三种Morris方法遍历，这一部分涉及到线索化二叉树，一般学校中数据结构与算法分析这门课会将的（反正博主上这门课的时候老师讲了），了解了线索化二叉树之后再看Morris遍历方法会简单很多。

plus：

这里我只写了中序遍历的三种方法，前序遍历和后序遍历思路和这差不多，如果后面我有时间，我会把前序遍历和后序遍历的三种方法代码补上 ~~（估计多半是没时间了）~~

写在最后

如果你觉得我写题解还不错的，请各位王子公主移步到我的其他题解看看

数据结构与算法部分（还在更新中）：

C++ STL总结 - 基于算法竞赛（强力推荐）
动态规划——01背包问题
动态规划——完全背包问题
动态规划——多重背包问题
动态规划——分组背包问题
最短路算法——Dijkstra（C++实现）
最短路算法———Bellman_Ford算法（C++实现）
最短路算法———SPFA算法（C++实现）
最小生成树算法———prim算法（C++实现）
最小生成树算法———Kruskal算法（C++实现）
染色法判断二分图（C++实现）

Linux部分（还在更新中）：

Linux学习之初识Linux
Linux学习之命令行基础操作