当前位置: 首页 > news >正文

【遍历】非递归法 二叉树的前中后序遍历

文章目录

    • 非递归法
      • 前序遍历
      • 后序遍历
      • 中序遍历
    • 递归法DFS

非递归法

通过栈Stack来模拟递归。

前序遍历

LeetCode 144
在这里插入图片描述

前序遍历:1 2 3

定义:存放答案的List、栈Stack

  1. 将root入栈
  2. 出栈:node,为null则舍弃
  3. 将node放入list
  4. 将node.right入栈
  5. 将node.left入栈
  6. 栈不为空则重复2-5步

为了让左节点优先于右节点出栈,因此先将右节点入栈。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> list = new LinkedList<>();stack.push(root);while(!stack.empty()){TreeNode node = stack.pop();if(node==null)continue;list.add(node.val);stack.push(node.right);stack.push(node.left);}return list;}
}

后序遍历

LeetCode 145
在这里插入图片描述

后序遍历:2 3 1

后序遍历仅需在前序遍历的代码中修改3处即可。

由前序遍历1 2 3 改为 1 3 2 再翻转为 2 3 1即为答案。

class Solution {public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> list = new LinkedList<>();stack.push(root);while(!stack.empty()){TreeNode node = stack.pop();if(node == null)continue;list.add(node.val);stack.push(node.left); // 先放入左节点stack.push(node.right); }Collections.reverse(list); // 反转return list;}
}

中序遍历

LeetCode 94

中序遍历代码与前序和后续不同。

在这里插入图片描述

中序遍历: 4 2 5 1 3。

思考:要想先输出4,则需要将左节点持续入栈,直到为null,此时出栈即为4,然后将其右节点入栈…

同样的,定义存放结果的list和栈stack。

  1. cur = root
  2. cur不为空或者栈不为空
  3. 循环 将cur入栈,并将cur赋值其左节点,直到为空
  4. 出站node,将node加入list
  5. 将node赋值为node.left
  6. 重复2 - 5步
class Solution {public List<Integer> inorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> list = new LinkedList<>();TreeNode cur = root;while(cur!=null||!stack.empty()){while(cur!=null){stack.push(cur);cur = cur.left;}TreeNode node = stack.pop(); list.add(node.val);cur = node.right;}return list;}
}

递归法DFS

class Solution {List<Integer> list1 = new LinkedList<>(); // 前序List<Integer> list2 = new LinkedList<>(); // 中序List<Integer> list3 = new LinkedList<>(); // 后序public List<Integer> inorderTraversal(TreeNode root) {traverse(root);return list2; }void traverse(TreeNode root){if(root==null)return;list1.add(root.val); traverse(root.left); // 递归左节点list2.add(root.val);traverse(root.right); // 递归右节点list3.add(root.val);}}

参考:

  • cyc2018
  • 代码随想录 B站
http://www.lryc.cn/news/119598.html

相关文章:

  • Python将tiff转换成png
  • 【大数据】-- 部署 Flink kubernetes operator
  • 能够完成两个数的算术运算的单地址指令,地址码指明一个操作数,另一个操作数来自( )方式
  • 数据库数据恢复-Oracle数据库数据恢复案例
  • 对于msvcr120.dll丢失的问题,分享几种解决方法
  • 网络安全进阶学习第十三课——SQL注入Bypass姿势
  • vue3 provide inject实现强制刷新
  • Neo4j笔记-数据迁移(导出/导入)
  • 请求转发和请求重定向
  • TOMCAT的多实例部署和动静分离
  • 阿里微服务seata组件tc告诉rm进行提交的时候,rm提交失败了seata怎么办呢?
  • 已解决 RuntimeError: There is no current event loop in thread ‘Thread-1‘.
  • Android的学习系列之Android Studio Setup安装
  • Python测试框架pytest:常用参数、查找子集、参数化、跳过
  • Android 13 Hotseat定制化修改
  • 【VUE】7、VUE项目中集成watermark实现页面添加水印
  • Rider无法识别Todo Comment
  • 用 docker 创建 jmeter 容器,能做性能测试?
  • Token 失效退出至登录页面
  • 微服务系列(2)--注册中心
  • VSCode使用CMake断点调试
  • Python爬虫异常处理心得:应对网络故障和资源消耗
  • 【CSS】CSS 布局——常规流布局
  • flutter开发实战-实现左右来回移动的按钮引导动画效果
  • ROS实现自定义信息以及使用
  • 初始C语言——详细讲解操作符以及操作符的易错点
  • 论文写作常用词句积累
  • 伺服系统::编码器
  • 计算机网络 数据链路层 虚拟局域网 VLAN
  • Git全栈体系(五)