solution.md

# 二叉树的中序遍历

<p>给定一个二叉树的根节点 <code>root</code> ，返回它的 <strong>中序</strong> 遍历。</p><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0094.Binary%20Tree%20Inorder%20Traversal/images/inorder_1.jpg" style="width: 202px; height: 324px;" /><pre><strong>输入：</strong>root = [1,null,2,3]<strong><br />输出：</strong>[1,3,2]</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>root = []<strong><br />输出：</strong>[]</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>root = [1]<strong><br />输出：</strong>[1]</pre><p><strong>示例 4：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0094.Binary%20Tree%20Inorder%20Traversal/images/inorder_5.jpg" style="width: 202px; height: 202px;" /><pre><strong>输入：</strong>root = [1,2]<strong><br />输出：</strong>[2,1]</pre><p><strong>示例 5：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0094.Binary%20Tree%20Inorder%20Traversal/images/inorder_4.jpg" style="width: 202px; height: 202px;" /><pre><strong>输入：</strong>root = [1,null,2]<strong><br />输出：</strong>[1,2]</pre><p> </p><p><strong>提示：</strong></p><ul>	<li>树中节点数目在范围 <code>[0, 100]</code> 内</li>	<li><code>-100 <= Node.val <= 100</code></li></ul><p> </p><p><strong>进阶:</strong> 递归算法很简单，你可以通过迭代算法完成吗？</p>
<p>以下<font color="red">错误</font>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
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

```cpp

```

## 答案

```cpp
class Solution
{
public:
    vector<int> inorderTraversal(TreeNode *root)
    {
        vector<int> result;
        return InorderTraversal(root, result);
    }

private:
    vector<int> InorderTraversal(TreeNode *root, vector<int> &result)
    {
        if (root == NULL)
            return result;
        InorderTraversal(root->left, result);
        InorderTraversal(root->right, result);
        result.push_back(root->val);
        return result;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    vector<int> inorderTraversal(TreeNode *root)
    {
        vector<int> res;
        stack<TreeNode *> 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

```cpp
class Solution
{
public:
    vector<int> inorderTraversal(TreeNode *root)
    {
        vector<int> ret;

        stack<TreeNode *> 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

```cpp
class Solution
{
private:
    void rec(TreeNode *root, vector<int> &ret)
    {
        if (root != NULL)
        {
            rec(root->left, ret);
            ret.push_back(root->val);
            rec(root->right, ret);
        }
    }

public:
    vector<int> postorderTraversal(TreeNode *root)
    {
        vector<int> ret;
        rec(root, ret);
        return ret;
    }
};
```