# 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[2,1]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
- 树中节点数目在范围
[0, 100] 内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
以下错误的选项是？
## aop
### before
```c
#include
using namespace std;
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) {}
};
```
### after
```c
```
## 答案
```c
class Solution
{
public:
vector inorderTraversal(TreeNode *root)
{
vector result;
return InorderTraversal(root, result);
}
private:
vector InorderTraversal(TreeNode *root, vector &result)
{
if (root == NULL)
return result;
InorderTraversal(root->left, result);
InorderTraversal(root->right, result);
result.push_back(root->val);
return result;
}
};
```
## 选项
### A
```c
class Solution
{
public:
vector inorderTraversal(TreeNode *root)
{
vector res;
stack s;
while (root != nullptr || !s.empty())
{
if (root != nullptr)
{
s.push(root);
root = root->left;
}
else
{
auto cur = s.top();
s.pop();
res.emplace_back(cur->val);
root = cur->right;
}
}
return res;
}
};
```
### B
```c
class Solution
{
public:
vector inorderTraversal(TreeNode *root)
{
vector ret;
stack toTraversal;
while (root != NULL || !toTraversal.empty())
{
while (root != NULL)
{
toTraversal.push(root);
root = root->left;
}
root = toTraversal.top();
toTraversal.pop();
ret.push_back(root->val);
root = root->right;
}
return ret;
}
};
```
### C
```c
class Solution
{
private:
void rec(TreeNode *root, vector &ret)
{
if (root != NULL)
{
rec(root->left, ret);
ret.push_back(root->val);
rec(root->right, ret);
}
}
public:
vector postorderTraversal(TreeNode *root)
{
vector ret;
rec(root, ret);
return ret;
}
};
```