声明：本文原题主要来自力扣，记录此博客主要是为自己学习总结，不做任何商业等活动！

二叉树的遍历有前序遍历、中序遍历、后序遍历和层次遍历，其中二叉树基本知识点可以参考博主上篇博客（二叉树基本知识点图文介绍(全网最简洁)_净无邪博客-CSDN博客），二叉树的前序遍历可以参考博主这篇博客（二叉树前序遍历(递归法和迭代法(即非递归法))——C++_净无邪博客-CSDN博客），本文主要总结二叉树的中序遍历。

一、二叉树中序遍历

中序遍历是先遍历左子节点left，在遍历父节点parent，最后遍历右子节点right，即遍历顺序：

left ——> parent ——> right

下面是力扣原题，写一个中序遍历程序。

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

1.1递归法

递归法主要用编译器栈自动压入递归的函数参数和局部变量，依次按照中序遍历顺序有且仅有一次访问二叉树。下面是具体示例代码：

/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return datas;
        if(root->left != nullptr)
            inorderTraversal(root->left);
        datas.push_back(root->val);
        if(root->right != nullptr)
            inorderTraversal(root->right);
        return datas;
    }

private:
    vector<int> datas;
};

结果：

 1.2迭代法

迭代法是采用非递归方法实现二叉树的中序遍历，主要利用数据结构std::stack来实现，利用栈std::stack的先进后出特性依次压入待访问的节点，然后依次按照中序遍历顺序弹出和访问节点，确保每个节点有且仅有一次访问。

具体步骤如下：

a1 先将所有父节点和左子节点依次压入栈；

这样做的目的是为了先弹出左子节点，再弹出父节点，可以在弹出左子节点的时候进行遍历，同时处理右节点，比如将右节点压入栈，这样就实现了先访问左节点，然后父节点，最后右子节点。

while (cur != nullptr)
{
    nodeStack.push(cur);
    cur = cur->left;
}

a2 然后弹出一个节点，进行遍历；

此时弹出的节点前提是左子节点为空，则该节点是父节点，故需要在后面遍历右子节点

cur = nodeStack.top();
nodeStack.pop();
datas.push_back(cur->val);

a3 遍历右子节点，将其作为一棵右子节点树的父节点，继续循环第a1步骤，直到整个栈为空即可

while (cur != nullptr || !nodeStack.empty())
{
    while (cur != nullptr) // 控制父节点和左子树非空，则先压入父节点，然后压入左节点
    {
        // 循环将做父节点和左子树压入栈 ......
    }
    // 弹出栈和遍历节点 ......
    cur = cur->right; // 将弹出栈的右子节点当作右子树的父节点进行循环遍历
}

下面是完整代码实现：

/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        std::stack<TreeNode *> nodeStack;
        while(cur != nullptr || !nodeStack.empty()) // 循环截止条件是父节点为空或栈为空
        {
            while(cur != nullptr) // 控制父节点和左子树非空，则先压入父节点，然后压入左节点
            {
                nodeStack.push(cur);
                cur = cur->left;
            }
            cur = nodeStack.top();
            nodeStack.pop();
            datas.push_back(cur->val);
            cur = cur->right; // 将弹出栈的右子节点当作父节点进行循环遍历
        }
        return datas;
    }
private:
    vector<int> datas;
};

结果：

1.3总结

二叉树的中序遍历递归法跟前序遍历差不多，但是迭代法在代码结构上却有较大差别，前序遍历主要通过一个栈先访问当前节点也就是父节点，然后再遍历左节点，接着遍历右节点，代码结构清晰易于理解；但是中序遍历的迭代法代码实现结构却不同，主要还是数据结构栈的性质，决定了中序遍历需要先将父节点压入栈，然后压入左节点，这是一个循环的步骤，直到左子树为空才停止压栈，此时需要弹出栈进行遍历该节点(可以看成父节点，左节点为空)，遍历完后再将该节点的右节点作为右子树的父节点，重复前面步骤，直到整个栈为空即可完成每个节点中序遍历。