94. 二叉树的中序遍历 - 力扣（LeetCode）

一、题目要求

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

二、解法1-递归 O(N)

        中序遍历的次序是 左-根-右，使用递归很简单就能写出来

class Solution {void _inorderTravinersal(TreeNode* root) {if (root == nullptr)return;_inorderTravinersal(root->left); // 左_v.push_back(root->val);         // 根_inorderTravinersal(root->right);// 右}
public:vector<int> inorderTraversal(TreeNode* root) {_inorderTravinersal(root);return _v;}
private:vector<int> _v;
};

三、解法2-迭代 进阶

        使用栈来模拟递归。

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> s;while (root != nullptr || s.empty() == false) {while (root != nullptr) {s.push(root);root = root->left;}root = s.top();s.pop();v.push_back(root->val);root = root->right; // 下一次循环检查是否有右}return v;}
};