题解 | #二叉树的中序遍历#

题目：二叉树的中序遍历
描述：给定一个二叉树的根节点root，返回它的中序遍历。
示例1：输入：{1,2,#,#,3}
返回值：[2,3,1]
说明：
图片说明

解法一：
思路分析：这道题大部分人应该很熟悉了，首先我们了解一下关于二叉树的中序遍历概念，什么是中序遍历呢，中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
——给定一个序列{A,B,C,D,E,F,G}，下面进行分析：
——在该二叉树中，首先访问左子树，因为根节点的左子树结点B还有左子树，所以继续往下遍历得到最左边的一个元素为D，然后寻找D的根节点为B，最后寻找B的右子树结点为E，所以其根节点的左子树结点中序遍历结果为{DBE}，在左子树遍历完成以后，遍历左子树的根节点为A，下面遍历A的右子树，寻找A中右子树的最左节点为F，寻找F的根节点为C，最后寻找C的右子树结点为G。最后输出二叉树的中序遍历为{DBEAFCG}。
——我们可以采用递归遍历的方法去解决问题。
实例分析：

图片说明
C++核心代码：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> mid;//设置一个存储容器
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        midprint(root);
        return mid;
    }
    void midprint(TreeNode* root){
        if(root == nullptr)
            return ;
        midprint(root->left);//首先寻找最左边的结点
        mid.push_back(root->val);//输出左子树的值
        midprint(root->right);//再寻找右子树
    }
};

——该递归序列需要将所有的元素值遍历一次，按照顺序返回最终序列，所以其时间复杂度为 $O(N)$ ，需要构建一个新的容器对象用来存储中序遍历的结果，所以其空间复杂度为 $O(N)$ 。

解法二：
思路分析：上述方法采用的是递归遍历实现，我们可以通过非递归+栈的方式实现中序遍历，在中序遍历中借助栈，首先压入顺序为左结点，根结点，右节点，进入循环的条件为判断栈是否为空，首先将左结点入栈，重复该过程，直到左节点不存在，然后依次出栈，出栈的同时判断当前结点的右子树是否存在，若存在则再次进入循环。
其C++核心代码为：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> mid;//设置一个存储容器
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        stack<TreeNode *> s;//设置栈对象
        while (s.size() || root){
            while (root){
                s.push(root);
                root = root->left;//先左
            }
            if (s.size()){
                root = s.top();
                s.pop();//出栈
                mid.push_back(root->val);//将值放入mid容器中
                root = root->right;//进入右子树
            }
        }
        return mid;
    }
};

——该程序通过非递归+栈的方式实现中序遍历，需要构造一个栈对象来辅助实现，同样需要遍历所有元素，所以其时间复杂度为 $O(N)$ ，需要构造一个返回的容器mid和一个保存的栈对象s，其空间复杂度为 $O(N)$ 。