题目：

原题链接
简述题目就是：给你一颗二叉树的根结点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中序遍历的前驱结点）

讯享网

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

代码

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：

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

写在最后

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

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

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

2. Linux部分（还在更新中）：

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

✨🎉总结

“种一颗树最好的是十年前,其次就是现在”
所以,
“让我们一起努力吧,去奔赴更高更远的山海”

如果有错误❌,欢迎指正哟😋

🎉如果觉得收获满满,可以动动小手,点点赞👍,支持一下哟🎉