【Hot 100 刷题计划】 LeetCode 94. 二叉树的中序遍历 | C++ 递归法 迭代法

LeetCode 94. 二叉树的中序遍历 题目描述题目级别简单给定一个二叉树的根节点root返回 它的中序遍历。示例 1:输入root [1,null,2,3]输出[1,3,2] 解法一递归的本质二叉树的中序遍历规则非常简单左子树 - 根节点 - 右子树。因为树本身就是一个天然的递归结构每一个子节点都可以看作是一棵新树的根所以使用递归解法最符合直觉先一头扎进左子树直到最底端。处理当前节点将值放入结果数组。再一头扎进右子树。细节优化为了防止在递归过程中不断创建新的结果数组我们只需在主函数创建一次vectorint res然后通过引用传递res把它交由递归函数去填充。这样极大提升了内存效率。 C 代码实现 (递归法)classSolution{public:vectorintinorderTraversal(TreeNode*root){vectorintres;// 将 res 以引用方式传入避免拷贝inorder(root,res);returnres;}voidinorder(TreeNode*root,vectorintres){// 递归终止条件遇到空节点直接返回if(!root)return;// 1. 遍历左子树inorder(root-left,res);// 2. 访问根节点将节点值存入结果res.push_back(root-val);// 3. 遍历右子树inorder(root-right,res);}}; 解法二用Stack手动模拟系统栈在递归写法中程序之所以能从底层一路“退回来”是因为操作系统帮我们在底层维护了一个“函数调用栈”。如果要求用迭代循环来实现我们就必须自己动手建一个栈 (stack) 来模拟这个回退的过程。核心运作机制一路向左撞墙回头准备一个指针curr指向根节点。“一路向左”只要curr不为空我们就一直顺着左子树往下走同时把路过的节点统统压入栈中。因为中序遍历要最后才访问这些父节点所以先用栈把它们存起来。“撞墙回头”当curr走到空碰壁了说明左边到底了。这时候我们就从栈顶弹出一个节点这个节点就是没有左孩子或者左孩子已经被访问过的最底层的节点。“访问与向右”把弹出的节点值加入结果数组。既然它的左边和自己都已经处理完了接下来就让curr指向它的右孩子准备开启下一轮同样的循环。 C 代码实现 (栈迭代法)classSolution{public:vectorintinorderTraversal(TreeNode*root){vectorintres;stackTreeNode*st;// 我们自己维护的调用栈TreeNode*currroot;// 游标指针// 循环条件只要游标还没走完或者栈里还有没处理完的节点就继续while(curr!nullptr||!st.empty()){// 阶段 1不断向左深入把沿途的节点统统压栈while(curr!nullptr){st.push(curr);currcurr-left;}// 阶段 2此时 curr 为空说明左边走到底了// 从栈顶取出一个节点退回上一步currst.top();st.pop();// 访问该节点存入结果数组res.push_back(curr-val);// 阶段 3转向该节点的右子树继续下一轮外层大循环currcurr-right;}returnres;}};