文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析递归解法空间复杂度O(n) 、时间复杂度O(n)迭代解法空间复杂度O(n)、时间复杂度O(n)2、解题代码递归解法空间复杂度O(n) 、时间复杂度O(n)迭代解法空间复杂度O(n)、时间复杂度O(n)三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接94.二叉树的中序遍历2、题目描述二、个人思路整理1、思路分析递归解法空间复杂度O(n) 、时间复杂度O(n)递归终止条件当前节点为空则直接返回递归体先递归遍历左子树访问根节点再递归遍历右子树。迭代解法空间复杂度O(n)、时间复杂度O(n)迭代解法即利用显式栈来模拟系统栈的递归行为。创建栈和一个遍历指针遍历指针一直向左将左节点依次入栈到达最左边没有左孩子时说明此节点是叶子节点或根节点弹栈并记录结果处理完左边弹栈记录完根节点或叶子节点后处理右子树。我的理解是先把左边左节点都入栈然后到达最左端后依次一层一层往上返处理每一层的右子树右节点当然右子树也可能存在左节点依次循环这样遍历即可每当没有左孩子时说明此节点是根节点或叶子节点记录到结果中即可下面为大模型相关解释防遗忘迭代过程就是一路向左推入栈无路可走弹栈输出然后向右迈一步。栈的作用暂存父节点方便在左子树处理完后能够“回溯”回来访问根节点和右子树。拆解为 3 个步骤往左走到底入栈指针不断往左孩子走沿途经过的所有节点都压入栈中保存因为左子树还没处理完当前节点还不能输出。弹栈输出访问“根”走到nullptr说明没有左孩子了时从栈中弹出一个节点。这就是当前子树最左边的节点或根节点记录它的值。往右迈一步转向右子树处理完当前节点后指针转向它的右孩子回到步骤 1继续重复对右子树执行相同的逻辑。为什么外层while需要cur ! nullptr || !st.empty()两个条件st.empty()为假栈不空时说明虽然当前节点走到了nullptr但栈里还压着之前的父节点需要弹出继续处理。cur ! nullptr为真时发生在刚转向右子树cur cur-right之后。此时栈可能恰好被弹空了比如刚处理完根节点但右子树里还有节点需要遍历必须靠cur ! nullptr才能进入循环继续压栈。2、解题代码递归解法空间复杂度O(n) 、时间复杂度O(n)/** * Definition for a binary tree node. * 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) {} * }; */classSolution{public:voidinorder(TreeNode*root,vectorintres){if(!root){return;}inorder(root-left,res);//左res.push_back(root-val);//根inorder(root-right,res);//右}vectorintinorderTraversal(TreeNode*root){vectorintres;inorder(root,res);returnres;}};迭代解法空间复杂度O(n)、时间复杂度O(n)/** * Definition for a binary tree node. * 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) {} * }; */classSolution{public:vectorintinorderTraversal(TreeNode*root){vectorintres;stackTreeNode*st;TreeNode*curroot;while(cur!nullptr||!st.empty()){//1. 一直向左将所有左节点入栈while(cur!nullptr){st.push(cur);curcur-left;//左}//2. 当没有左孩子即到达最左边时弹出栈顶元素curst.top();st.pop();res.push_back(cur-val);//中//3. 根节点处理完转向处理右子树curcur-right;//右}returnres;}};三、知识风暴中序遍历中序遍历是二叉树深度优先搜索DFS的一种常见方式其遍历规则为左子树-根节点-右子树。该算法时间复杂度与空间复杂度计算时间复杂度O ( n ) O(n)O(n)n为二叉树的节点总数每个节点进入inorder函数后执行的操作为O ( 1 ) O(1)O(1)总耗时为n × O ( 1 ) O ( n ) n \times O(1) O(n)n×O(1)O(n)。空间复杂度O ( n ) O(n)O(n)空间复杂度取决递归调用栈的最大深度。最好/平均情况平衡二叉树树高log ⁡ 2 n \log_2 nlog2​n调用栈最多同时保存log ⁡ 2 n \log_2 nlog2​n层函数空间复杂度为O ( log ⁡ n ) O(\log n)O(logn)最坏情况单链树二叉树退化成一条链调用栈的最大深度达到n nn空间复杂度为O ( n ) O(n)O(n)。