leetcode145. 二叉树的后序遍历,递归法+迭代法,全过程图解+步步解析,一点点教会你迭代法后序遍历
创始人
2024-12-29 09:06:56
0次

leetcode145. 二叉树的后序遍历,递归法+迭代法

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。
示例 1:
在这里插入图片描述
输入:root = [1,null,2,3]
输出:[3,2,1]

示例 2:
输入:root = []
输出:[]

示例 3:
输入:root = [1]
输出:[1]

递归法还是一如既往的简单。

postorder函数是递归函数,用于辅助实现后序遍历。它接收两个参数:一个指向当前节点的指针root和一个用于存储遍历结果的向量res。函数首先检查当前节点是否为空,如果是,则直接返回。如果不为空,则递归调用自身,先遍历左子树,再遍历右子树。在遍历完左右子树后,将当前节点的值添加到结果向量res中。

postorderTraversal函数是对外提供的公共接口,用于获取二叉树的后序遍历结果。它接收一个参数:一个指向二叉树根节点的指针root。函数首先初始化一个空的结果向量res,然后调用postorder函数进行后序遍历,并将遍历结果存储在res中。遍历完成后,返回这个结果向量。

整个实现过程是典型的递归方法,通过递归调用自身来遍历二叉树的每一个节点。递归的终止条件是当前节点为空,这时函数会返回而不执行任何操作。
在这里插入图片描述

class Solution { public:     void postorder(TreeNode *root, vector &res) {         if (root == nullptr) {             return;         }         postorder(root->left, res);         postorder(root->right, res);         res.push_back(root->val);     }      vector postorderTraversal(TreeNode *root) {         vector res;         postorder(root, res);         return res;     } };  

二叉树后序遍历的迭代法相对前序和中序来说就要难一点了,

定义辅助栈:使用一个stack类型的栈stk来辅助遍历。

定义前一个访问节点:定义一个TreeNode *类型的指针prev,用来记录上一个被访问的节点。

迭代遍历:使用一个while循环,条件是root不为空或栈stk不为空。这个循环将一直执行,直到所有节点都被访问。

向左下推:内部的第一个while循环将root沿着左子树一直推到最底部,直到遇到空节点。每次迭代,都将当前节点压入栈中,并更新root为当前节点的左子节点。

处理当前节点:当左子树被完全遍历后,root将变为nullptr,此时从栈中弹出栈顶元素,即当前节点。

后序遍历条件判断:
如果当前节点的右子节点为空,或者右子节点已经访问过(即root->right == prev),则将当前节点的值添加到结果向量res中,并将prev更新为当前节点,然后将root设置为nullptr,准备处理下一个节点。
如果当前节点的右子节点不为空且未访问过,则将当前节点再次压入栈中,并更新root为当前节点的右子节点,继续遍历右子树。
在这里插入图片描述
1.我们再以这个图为例,首先向左下推直到D,ABD都入栈了,这时候判断D的左子树为null,于是弹出栈顶D,D没有右子树,于是D首先被遍历进结果数组,并将前一个访问节点记录为D,将root变成null,方便处理下一个节点。

2.接下来弹出栈顶元素B,B有右节点且前一个访问节点不是B的右节点,所以把B再推入栈,访问B的右节点F。

3.F有左节点,于是F入栈,E入栈,E没有左节点,E出栈。E也没有右节点,于是E第二个被遍历进结果数组,并将前一个访问节点记录为E,将root变成null,方便处理下一个节点。

4.再弹出栈顶元素F,F没有右节点,于是F第三个被遍历进结果数组,并将前一个访问节点记录为F,将root变成null,方便处理下一个节点。

5.再弹出栈顶元素B,B有右节点,但是!!前一个访问节点是B的右节点F,所以B第四个被遍历进结果数组,并将前一个访问节点记录为B,将root变成null,方便处理下一个节点。

依此类推遍历完全部节点DEFBHGICA。
做完此题,二叉树的中序遍历就再简单不过了,可以秒杀。
具体题目如下。

leetcode94二叉树的中序遍历

我也写了二叉树中序遍历的题解,可以去看看。相对二叉树的中序遍历,后序遍历的迭代法确实难了不少,值得反复学习。

相关内容

热门资讯

一分钟了解开挂!友空互娱开挂多... 一分钟了解开挂!友空互娱开挂多功能AI方法,友空互娱真是是有开挂方法1、友空互娱脚本辅助下载、友空互...
我来教大家透视挂!葫芦娃大厅透... 我来教大家透视挂!葫芦娃大厅透视挂多功能AIapp,葫芦娃大厅其实是真的有透视挂app1、超多福利:...
玩家必看科普开挂!福城娱乐开挂... 玩家必看科普开挂!福城娱乐开挂多功能AI插件,福城娱乐切实真的是有开挂插件1、打开软件启动之后找到中...
玩家必看科普外挂!海螺互娱外挂... 玩家必看科普外挂!海螺互娱外挂多功能AI方法,海螺互娱其实是真的有外挂方法1、实时海螺互娱透视辅助更...
盘点十款开挂!开心娱乐开挂多功... 盘点十款开挂!开心娱乐开挂多功能AI工具,开心娱乐一直真的有开挂工具1、盘点十款开挂!开心娱乐开挂多...
发现玩家外挂!神牛大厅外挂多功... 发现玩家外挂!神牛大厅外挂多功能AI软件,神牛大厅切实真的是有外挂软件1、玩家可以在神牛大厅透视最简...
技巧知识分享外挂!西兵外挂多功... 技巧知识分享外挂!西兵外挂多功能AI攻略,西兵果然真的是有外挂攻略西兵透视方法中分为三种模型:西兵靠...
实测交流作弊器!七天娱乐作弊器... 实测交流作弊器!七天娱乐作弊器多功能AIapp,七天娱乐总是真的有作弊器app进入游戏-大厅左侧-新...
一分钟揭秘外挂!欢盈娱乐外挂多... 一分钟揭秘外挂!欢盈娱乐外挂多功能AI软件,欢盈娱乐确实真的有外挂软件小薇(辅助器软件下载)致您一封...
科技通报透视挂!豪发娱乐透视挂... 科技通报透视挂!豪发娱乐透视挂多功能AI插件,豪发娱乐总是真的是有透视挂插件1、每一步都需要思考,不...