Leetcode 145:二叉树的后序遍历(迭代法)

ops/2024/10/22 2:56:38/

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 

思路:

迭代法的思路是,使用栈,一层一层的将树节点遍历入栈。

比如下面这个树,使用迭代法,1)第一层,让根节点入栈。2)第二层,弹出第一层的节点,让第一层的孩子入栈(先左再右)。3)第三层,依次弹出第二层元素,让其子节点入栈。

结果为,第一步:5入栈,出栈,result中存储5;

              第二步:4,6依次入栈;6无子节点,所有6出栈,result中存储6;

              第三步:4出栈,result存储4。同时,4的子节点1、2先后入栈。因为这两个子节点都无孩子节点,所有2,1出栈,result中存储2,1。

          至此,result中存储值为5、6、4、2、1;

          翻转后为1,2,4,6,5

//后序遍历//迭代法:重复执行一段代码来求解//利用栈,先将根节点的右孩子放进栈,再将左孩子放进栈public static List<Integer> postorderTraversal(TreeNode root){List<Integer> result=new ArrayList<>();Stack<TreeNode> stack=new Stack<>();if(root!=null){stack.push(root);}while (!stack.empty()){TreeNode node=stack.pop();   //取栈顶元素result.add(node.val);if(node.left!=null){stack.push(node.left);     //左节点入栈}if(node.right!=null){stack.push(node.right);    //右节点入栈}}Collections.reverse(result);     //翻转Listreturn result;}


http://www.ppmy.cn/ops/27176.html

相关文章

赶紧收藏!2024 年最常见 100道 Java 基础面试题(二十二)

上一篇地址&#xff1a;赶紧收藏&#xff01;2024 年最常见 100道 Java 基础面试题&#xff08;二十一&#xff09;-CSDN博客 四十三、线程的run()和start()有什么区别&#xff1f; 在Java中&#xff0c;run()方法和start()方法都是与线程&#xff08;Thread&#xff09;相关…

iA Writer for Mac:简洁强大的写作软件

在追求高效写作的今天&#xff0c;iA Writer for Mac凭借其简洁而强大的功能&#xff0c;成为了许多作家、记者和学生的首选工具。这款专为Mac用户打造的写作软件&#xff0c;以其独特的设计理念和实用功能&#xff0c;助你轻松打造高质量的文章。 iA Writer for Mac v7.1.2中文…

Zapier 与生成式 AI 的自动化(三)

原文&#xff1a;zh.annas-archive.org/md5/057fe0c351c5365f1188d1f44806abda 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 第九章&#xff1a;探索内置应用程序来提取和编译数据 正如我们在第六章中讨论的&#xff0c;创建多步 Zaps 和使用内置应用程序&#xff…

【笔试题汇总】华为春招笔试题解 2024-4-17

这里是paoxiaomo&#xff0c;一个现役ACMer&#xff0c;之后将会持续更新算法笔记系列以及笔试题题解系列 本文章面向想打ICPC/蓝桥杯/天梯赛等程序设计竞赛&#xff0c;以及各个大厂笔试的选手 感谢大家的订阅➕ 和 喜欢&#x1f497; 有什么想看的算法专题可以私信博主 &…

安装Kuboard管理k8s

一、Kuboard 介绍 Kuboard 是一款免费的 Kubernetes 管理工具,提供了丰富的功能,结合已有或新建的代码仓库、镜像仓库、CI/CD工具等,可以便捷的搭建一个生产可用的 Kubernetes 容器云平台,轻松管理和运行云原生应用。您也可以直接将 Kuboard 安装到现有的 Kubernetes 集群…

SSH远程登录实操实验!

ssh远程登录协议&#xff1a;默认端口号22 以下实验7-2是服务端&#xff0c;7-1是客户端 服务器的相关信息&#xff1a; 服务名称&#xff1a;sshd 服务端主程序&#xff1a;/usr/sbin/sshd 服务端配置文件&#xff1a;/etc/ssh/sshd_config 客户端相关信息&#xff1a; …

ChatGPT向付费用户推“记忆”功能,可记住用户喜好 | 最新快讯

4月30日消息&#xff0c;人工智能巨头OpenAI宣布&#xff0c;其开发的聊天机器人ChatGPT将在除欧洲和韩国以外的市场全面上线“记忆”功能。这使得聊天机器人能够“记住”ChatGPT Plus付费订阅用户的详细信息&#xff0c;从而提供更个性化的服务。 OpenAI早在今年2月就已经宣布…

【综述】多核处理器芯片

文章目录 前言 Infineon处理器 AURIX™系列 TC399XX-256F300S 典型应用 开发工具 参考资料 前言 见《【综述】DSP处理器芯片》 Infineon处理器 AURIX™系列&#xff0c;基于TriCore内核&#xff0c;用于汽车和工业领域。 XMC™系列&#xff0c;基于ARM Cortex-M内核&…