1.题目介绍

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

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

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

2.题解

2.1 递归

首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。递归终止的条件为碰到空节点。

代码

//
// Created by trmbh on 2023-10-26.
// 94.二叉树中序遍历

#include<iostream>
#include<vector>
#include<string>

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:
    std::vector<int> inorderTraversal(TreeNode *root) {
        using namespace std;
        if (root == nullptr) return arr;
        else {
            inorderTraversal(root->left);
            arr.push_back(root->val);
            inorderTraversal(root->right);
        }
        return arr;
    }

private:
    std::vector<int> arr;
};

int main(){
    Solution solution;
    TreeNode n1(3);
    TreeNode n2(2, &n1, nullptr);
    TreeNode n(1, nullptr,&n2);
    std::vector<int> arr = solution.inorderTraversal(&n);
    for (int num:arr){
        std::cout << num << ' ';
    }
}

2.2迭代

思路

在递归中，我们其实隐式地使用了栈来保存前面节点的信息；所以这里如果我们要使用迭代的方法的话，就应该使用显式栈来保存节点信息，并在返回时提供节点信息。

这里大循环的终止条件是节点遍历完毕且栈空（若栈非空，代表还有前置节点需要回退）

代码

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