题意整理：

既对一颗以根节点给出的树进行中序遍历。
二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历树，而在访问左子树及右子树的时候按照同样的方式遍历，遇到空节点返回，直到遍历完整棵树。

方法一：递归实现

核心思想：

按照中序遍历的意义，很容易想出递归实现，既创建递归函数dfs(root)，如果root为空则返回，否则对左节点调用dfs函数，再将当前节点值加入答案数组，之后对右节点调用dfs函数

核心代码：

class Solution {
public:
    vector<int> ans;
    void dfs(TreeNode* root) {
        if(root == nullptr) {
            return;
        }
        dfs(root->left);
        ans.push_back(root->val);
        dfs(root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

复杂度分析：

时间复杂度：。其中n为二叉树节点的个数。二叉树的遍历中每个节点只会被访问一次。
空间复杂度：,空间复杂度取决于递归的栈深度，在二叉树退化为链表时达到最坏情况为

方法二：迭代实现

核心思想：

方法一的递归函数也可以用迭代实现，既将递归时的隐式栈显式地模拟出来。

核心代码：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> sk;
        while(root != nullptr || !sk.empty()) {
            //此时还有节点未加入
            while (root != nullptr) {
                //一直达到最左节点，中间节点全部入栈
                sk.push(root);
                root = root->left;
            }
            root = sk.top();
            sk.pop();
            //取出当前节点加入
            ans.push_back(root->val);
            root = root->right;//处理右节点
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：。其中n为二叉树节点的个数。二叉树的遍历中每个节点只会被访问一次。
空间复杂度：,空间复杂度取决于栈的深度，在二叉树退化为链表时达到最坏情况为