递归法
当我们在函数中调用函数时，外层函数就会被操作系统暂停，然后将外层函数的状态压入系统函数调用栈中，再去执行新的函数
由于系统函数调用栈空间往往是很小的，一旦深度达到了数万层，函数调用栈就会被撑爆，导致崩溃，并且由于系统函数调用栈位于底层，每一次涉及的操作都会影响一系列底层逻辑，使得开销和运行速度大大增加
树节点定义
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode() : val(0), left(nullptr), right(nullptr){} TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr) : val(val), left(left), right(right) {} };中序遍历的遍历顺序是左节点中节点右节点（对一颗最小二叉树而言）
- 整体思路
一颗二叉树应该先一直迭代左节点，直至最左边的叶子节点，然后将每一个节点都当作基于该节点为根节点的一颗独立子树（非常重要，贯穿整个树）来遍历，于是将中序遍历一个最小二叉树的方法封装成一个函数来不断嵌套不断迭代
中序遍历一颗最小二叉树函数（不唯一）：
我们开始思考该遍历函数的具体思路：
对于一个最小二叉树（一共只有三个节点），在我们只知道根节点的情况下，要实现中序遍历，最核心的代码只有3行
(仅作思路示范)
vector<int> res{}; void inorder(TreeNode* root) { res.push_back(root->left->val); res.push_back(root->val); res.push_back(root->right->val); }那么如何将其运用在整颗二叉树呢？
最关键的一句话：每一个节点都当作基于该节点为根节点的一颗独立子树
所以我们需要在每一个访问左右子节点的步骤中加入迭代。
注意有空树的可能，所以要加上判断条件
void inorder(TreeNode* root， vector<int>& res) { if(root != nullptr)// { //左节点 inorder(root->left, res); //中节点 res.push_back(root->val); //右节点 inorder(root->right, res); } return; } vector<int> inorderTraversal(TreeNode* root) { vector<int> result{}; inorder(root, result); return result; }迭代法
由于迭代法与的递归法基本原理相似（递归法使用的是隐式的函数调用栈，由系统自己维护，迭代法需要我们自己手动维护栈结构来实现）我们这道题也可以自己维护栈来代替递归法
由于栈结构由我们自己维护在堆上，所以很难发生栈溢出，同时省去系统维护带来的底层频繁创建销毁函数调用而带来的巨大开销
根据中序遍历（左->中->右），我们从根节点出发，应该先访问其左节点是否存在，若不存在则就直接录入根节点值然后再访问右节点；
若存在，注意每一个节点都当作基于该节点为根节点的一颗独立子树来处理，所以我们要先不断向左迭代，直至最左叶子节点，同时要记录向左迭代时经过的每一个节点
所以
vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; TreeNode* curr = root;//为了防止丢失整棵树的位置，我们需要用另一个节点来共同指向根节点 ...什么条件下开始迭代处理呢？
- 当栈中还有节点没处理即整棵树还没遍历完
- 当前节点不为空
但是两者之间关系又该是如何呢？无论是栈中还有节点没处理（父节点没遍历）还是当前节点不为空，可能存在子节点，只要二者满足其一就可以正常迭代
while(curr != nullptr || !st.empty()) { }现在不断向左子节点迭代并保存，只要当前节点不为空都要向左寻找子节点
while(curr != nullptr || !st.empty()) { while(curr != nullptr) { st.push(curr); curr = curr->left; }//结束时curr == nullptr * }此时curr为空，意味着左侧已经无路可走，我们必须利用栈顶元素（上一个路过的父节点）进行回溯
这时候根据中序遍历，由于左节点为空，所以要录入中节点st.top()->val（别忘了用完这个节点就st.pop()）以及向右寻找是否存在节点
while(curr != nullptr || !st.empty()) { while(curr != nullptr) { st.push(curr); curr = curr->left; }//结束时curr == nullptr * curr = st.top(); st.pop(); res.push_back(curr->val); curr = curr->right; }所以完整code：
vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; TreeNode* curr = root; while(curr != nullptr || !st.empty()) { while(curr != nullptr) { st.push(curr); curr = curr->left; } curr = st.top(); st.pop(); result.push_back(curr->val); curr = curr -> right; } return result; }
