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

算法1：递归

时间复杂度：$O(n)$

空间复杂度：最坏情况下需要空间 $O(n)$ ，平均情况为 $O(\log n)$

思路：可以使用递归进行中序遍历，先遍历左子树，再输出当前节点，最后遍历右子树。

C++ 代码

class Solution { public: vector inorderTraversal(TreeNode* root) { vector res; inorder(root, res); return res; }

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

};

算法2：迭代

时间复杂度：$O(n)$

空间复杂度：最坏情况下需要空间 $O(n)$ ，平均情况为 $O(\log n)$

思路：使用栈进行迭代。首先将根节点入栈，然后依次将根节点的左子节点入栈，直到左子树为空。然后弹出栈顶节点，输出其值，并将其右子节点入栈，继续以上操作。当栈为空时，遍历结束。

C++ 代码

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