1、解题思路

中序遍历是二叉树的经典遍历方式之一，顺序为：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。可以通过递归或迭代（使用栈）的方式实现中序遍历。

2、代码实现

C++ （递归）
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        vector<int> result;
        inorder(root, result);
        return result;
    }

  private:
    void inorder(TreeNode* root, vector<int>& result) {
        if (root == nullptr) {
            return ;
        }

        inorder(root->left, result);    // 遍历左子树
        result.push_back(root->val);    // 访问根节点
        inorder(root->right, result);   // 遍历右子树
    }
};
C++ （迭代）
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        vector<int> result;
        stack<TreeNode*> s;
        TreeNode* cur = root;

        while (cur != nullptr || !s.empty()) {
            while (cur != nullptr) {
                s.push(cur);
                cur = cur->left;    // 左子树入栈
            }

            cur = s.top();
            s.pop();
            result.push_back(cur->val); // 访问根节点
            cur = cur->right;   // 转向右子树
        }

        return result;
    }
};
Python （递归）
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#

from typing import List, Optional

class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        result = []
        self.inorder(root, result)
        return result

    def inorder(self, root: Optional[TreeNode], result: List[int]) -> None:
        if root is None:
            return
        self.inorder(root.left, result)  # 遍历左子树
        result.append(root.val)          # 访问根节点
        self.inorder(root.right, result) # 遍历右子树
Python （递归）
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#

from typing import List, Optional

class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        result = []
        stack = []
        curr = root

        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left         # 左子树入栈
            curr = stack.pop()
            result.append(curr.val)      # 访问根节点
            curr = curr.right            # 转向右子树

        return result

3、复杂度分析

  • 时间复杂度：O(n)，每个节点被访问一次。
  • 空间复杂度：递归方法为 O(n)（最坏情况），迭代方法同样为 O(n)。