题目

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

示例：
[容易] 94. 二叉树的中序遍历 - 图1

输入：root = [1,null,2,3]
输出：[1,3,2]

输入：root = []
输出：[]

解答 & 代码

解法一：递归

时间复杂度 O(n)：n 是二叉树的节点数

空间复杂度 O(d)：d 是二叉树的深度，最坏情况下，二叉树是一条链，则空间复杂度 O(n)

/**
* Definition for a binary tree node.
* 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) {}
* };
*/
class Solution {
  void inorder(TreeNode* root, vector<int>& result)
  {
      if(root->left)
          inorder(root->left, result);

      result.push_back(root->val);

      if(root->right)
          inorder(root->right, result);
  }
public:
  vector<int> inorderTraversal(TreeNode* root) {
      vector<int> result;
      if(root)
          inorder(root, result);
      return result;
  }
};

执行结果： ``` 执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户内存消耗：8.1 MB, 在所有 C++ 提交中击败了 72.37% 的用户

<a name="QGaKL"></a>
## 解法二：迭代

- 时间复杂度 O(n)：n 是二叉树的节点数
- 空间复杂度 O(d)：d 是二叉树的深度，最坏情况下，二叉树是一条链，则空间复杂度 O(n)
```cpp
/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> nodeS;
        // 遍历节点，直到 root 为空且栈为空
        while(root != nullptr || !nodeS.empty())
        {
            // 一直往左子树方向走，走的过程中将节点压入栈，直到 root == nullptr
            while(root != nullptr)
            {
                nodeS.push(root);
                root = root->left;
            }
            // 此时 root == nullptr，说明上一步的 root 没有左子树，即左边走到头了

            // 从栈中弹出节点并将节点值保存到结果数组中
            root = nodeS.top();             // root 指回上一步的 root
            nodeS.pop();                    // 出栈
            result.push_back(root->val);    // 压入结果数组
            // 然后转向右节点，继续上面的过程
            root = root->right;             // 访问右节点
        }

        return result;
    }
};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：8.2 MB, 在所有 C++ 提交中击败了 32.21% 的用户