递归法当我们在函数中调用函数时外层函数就会被操作系统暂停然后将外层函数的状态压入系统函数调用栈中再去执行新的函数由于系统函数调用栈空间往往是很小的一旦深度达到了数万层函数调用栈就会被撑爆导致崩溃并且由于系统函数调用栈位于底层每一次涉及的操作都会影响一系列底层逻辑使得开销和运行速度大大增加树节点定义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行(仅作思路示范)vectorint 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 vectorint res) { if(root ! nullptr)// { //左节点 inorder(root-left, res); //中节点 res.push_back(root-val); //右节点 inorder(root-right, res); } return; } vectorint inorderTraversal(TreeNode* root) { vectorint result{}; inorder(root, result); return result; }迭代法由于迭代法与的递归法基本原理相似递归法使用的是隐式的函数调用栈由系统自己维护迭代法需要我们自己手动维护栈结构来实现我们这道题也可以自己维护栈来代替递归法由于栈结构由我们自己维护在堆上所以很难发生栈溢出同时省去系统维护带来的底层频繁创建销毁函数调用而带来的巨大开销根据中序遍历左-中-右我们从根节点出发应该先访问其左节点是否存在若不存在则就直接录入根节点值然后再访问右节点若存在注意每一个节点都当作基于该节点为根节点的一颗独立子树来处理所以我们要先不断向左迭代直至最左叶子节点同时要记录向左迭代时经过的每一个节点所以vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* 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; }所以完整codevectorint inorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* 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; }