一篇文章教你如何用多种迭代写法实现二叉树遍历

目录
  • 思想
  • 实现
  • 总结

思想

利用栈和队列都可以实现树的迭代遍历。递归的写法将这个遍历的过程交给系统的堆栈去实现了,所以思想都是一样的、无非就是插入值的时机不一样。利用栈的先进先出的特点,对于前序遍历、我们可以先将当前的值放进结果集中,表示的是根节点的值、然后将当前的节点加入到栈中、当前的节点等于自己的left、再次循环的时候、也会将left作为新的节点、直到节点为空、也就是走到了树的最左边、然后回退、也就是弹栈、、也可以认为回退的过程是从低向上的、具体就是让当前的节点等于栈弹出的right、继续重复上面的过程,也就实现了树的前序遍历、也就是bfs.后续遍历、中序遍历思想也是类似的。

实现

    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                res.add(root.val);
                stack.add(root);
                root = root.left;
            }
            TreeNode cur = stack.pop();
            root = cur.right;
        }
        return res;
    }
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                res.add(root.val);
                stack.add(root);
                root = root.left;
            } else {
                TreeNode cur = stack.pop();
                root = cur.right;
            }
        }
        return res;
    }
    public List<Integer> preorderTraversal3(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
        return res;
    }
    public List<Integer> preorderTraversal4(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            res.add(root.val);
            if (root.right != null) {
                queue.addFirst(root.right);
            }
            if (root.left != null) {
                root = root.left;
                while (root != null) {
                    res.add(root.val);
                    if (root.right != null) {
                        queue.addFirst(root.right);
                    }
                    root = root.left;
                }
            }
        }
        return res;
    }
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.add(root);
                root = root.left;
            } else {
                TreeNode cur = stack.pop();
                res.add(cur.val);
                root = cur.right;
            }
        }
        return res;
    }
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.add(root);
                root = root.left;
            }
            TreeNode cur = stack.pop();
            res.add(cur.val);
            root = cur.right;
        }
        return res;
    }
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty()) {
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.right;
            }
            TreeNode cur = stack.pop();
            root = cur.left;
        }
        Collections.reverse(res);
        return res;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null)return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size!=0){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!= null){
                    queue.offer(cur.right);
                }
                size --;
            }
            ret.add(list);
        }
        return ret;
    }

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

    本文实例讲述了JavaScript数据结构与算法之二叉树遍历算法.分享给大家供大家参考,具体如下: javascript数据结构与算法--二叉树遍历(先序) 先序遍历先访问根节点, 然后以同样方式访问左子树和右子树 代码如下: /* *二叉树中,相对较小的值保存在左节点上,较大的值保存在右节点中 * * * */ /*用来生成一个节点*/ function Node(data, left, right) { this.data = data;//节点存储的数据 this.left = left;

  • Java 二叉树遍历的常用方法

    采用前序遍历.中序遍历.后续遍历实现时,即便采用不同的实现方式(递归方式.非递归),它们的算法结构是有很大的相似性.因而针对前三种的遍历我们会总结出对应通用的解决框架,便于在解决二叉树问题时进行使用. 递归方式 递归方式遍历二叉树时,无论是 前序遍历.中序遍历 还是 后续遍历 的方式,它们最大的区别就是对节点数据的访问位置不同.除此之外其结构完全一致,因而我们总结出如下的框架结构: void traverse(TreeNode root) { //终止条件 if(root == null) re

  • php实现的二叉树遍历算法示例

    本文实例讲述了php实现的二叉树遍历算法.分享给大家供大家参考,具体如下: 今天使用php来实现二叉树的遍历 创建的二叉树如下图所示 php代码如下所示: <?php class Node { public $value; public $child_left; public $child_right; } final class Ergodic { //前序遍历:先访问根节点,再遍历左子树,最后遍历右子树:并且在遍历左右子树时,仍需先遍历根节点,然后访问左子树,最后遍历右子树 public s

  • java实现二叉树遍历的三种方式

    本文实例为大家分享了java实现二叉树遍历的具体代码,供大家参考,具体内容如下 二叉树如下: 遍历结果如下: 以下是实现代码: package binTree; import java.util.Stack; /** * @author bin.zhang * @version 2017年8月29日 上午10:22:01 */ public class BinTreeTraversal { public static void main(String[] args) { System.out.p

  • C语言实现二叉树遍历的迭代算法

    本文实例讲述了C语言实现二叉树遍历的迭代算法,是数据结构算法中非常经典的一类算法.分享给大家供大家参考. 具体实现方法如下: 二叉树中序遍历的迭代算法: #include <iostream> #include <stack> using namespace std; struct Node { Node(int i, Node* l = NULL, Node* r = NULL) : item(i), left(l), right(r) {} int item; Node* le

  • 一篇文章教你如何用多种迭代写法实现二叉树遍历

    目录 思想 实现 总结 思想 利用栈和队列都可以实现树的迭代遍历.递归的写法将这个遍历的过程交给系统的堆栈去实现了,所以思想都是一样的.无非就是插入值的时机不一样.利用栈的先进先出的特点,对于前序遍历.我们可以先将当前的值放进结果集中,表示的是根节点的值.然后将当前的节点加入到栈中.当前的节点等于自己的left.再次循环的时候.也会将left作为新的节点.直到节点为空.也就是走到了树的最左边.然后回退.也就是弹栈..也可以认为回退的过程是从低向上的.具体就是让当前的节点等于栈弹出的right.继

  • 一篇文章教你如何用Java自定义一个参数校验器

    目录 注解 校验器 异常处理 测试 总结 自定义一个唯一字段校验器 注解 @Target({ElementType.FIELD}) @Retention(RetentionPolicy.RUNTIME) @Documented @Constraint(validatedBy = {IsUniqueValidator.class}) // 指定自定义的校验器 public @interface IsUnique { // 提示信息 String message() default "";

  • 一篇文章教你如何用C语言实现strcpy和strlen

    目录 自己实现strcpy.strlen strcpy的实现 strlen的实现 总结 自己实现strcpy.strlen strcpy的实现 思路: 通过指针访问地址然后将要copy的文本逐一复制到目的地. void my_strcpy(char* dest, char* src){ while (*src !='\0'){ *dest = *src; src++; dest++; } *dest = *src; } //自己实现strcpy int main(){ char arr1[]="

  • 一篇文章教你学会使用Python绘制甘特图

    目录 优点 局限 一日一书 用来制作甘特图的专业工具也不少,常见的有:Microsoft Office Project.GanttProject.WARCHART XGantt.jQuery.Gantt.Excel等,网络上也有一些优质工具支持在线绘制甘特图. 可是这种现成的工具,往往也存在一些弊端,让编程人员不知所措.比如说,花里胡哨的UI,让人目不暇接,不知点哪个才好: 比如说,有些基于浏览器的图表需要掌握HTML.JS等编程语言,只会点Python的我直接被劝退: 再比如,进来就是注册.登

  • 一篇文章教你使用SpringBoot如何实现定时任务

    前言 在 Spring + SpringMVC 环境中,一般来说,要实现定时任务,我们有两中方案,一种是使用 Spring 自带的定时任务处理器 @Scheduled 注解,另一种就是使用第三方框架 Quartz ,Spring Boot 源自 Spring+SpringMVC ,因此天然具备这两个 Spring 中的定时任务实现策略,当然也支持 Quartz,本文我们就来看下 Spring Boot 中两种定时任务的实现方式. 一.第一种方式:@Scheduled 使用 @Scheduled

  • 一篇文章教你学会js实现弹幕效果

    目录 新建一个html文件: 建好html文件,搞出初始模版 HTML添加 CSS填充 js逻辑代码 动画效果 下面是弹幕效果 : 相信小伙伴们都看过了,那么它实现的原理是什么呢,那么我们前端怎么用我们web技术去实现呢?? 新建一个html文件: 哈哈哈,大家别像我一样用中文命名. 中文命名是不合规范的,行走江湖,大佬们看见你的中文命名会笑话你的. 上图中,我们引入了jquery插件,没错我们用jq写,回归原始(找不到cdn链接的小伙伴可以百度bootcdn,在里面搜索jquery).并且取了

  • 一篇文章教你3分钟如何发布Qt程序

    导读:Qt程序编写好以后该如何发布.本文教你使用Qt自带工具windeployqt来进行操作. 本文字数:500,阅读时长大约:3分钟 (1)编写一个简单的程序 我们先做一个简单的窗口,添加一个图片资源文件,放置到窗口当中. 选择添加Qt Resource File文件类型 选择资源文件的路径,并为它命名 点击完成 设置资源前缀,如果资源层次不是很复杂的话,可以只设置一层,用"/"表示 点击Add Files添加一个图片文件 在主窗口中添加一个 Tool Button,设置刚才的图片为

  • 一篇文章教你用python画动态爱心表白

    初级画心 学Python,感觉你们的都好复杂,那我来个简单的,我是直接把心形看作是一个正方形+两个半圆: 于是这就很简单了,十行代码解决: import turtle as t t.pensize(2) # 笔大小2像素 t.pencolor("red") # 颜色为红色 t.left(45) # 45度 t.fd(200) # 向前200直线 t.circle(100, 180) # 画一圆半径100 弧度180 t.right(90) # 向右90度 t.circle(100, 1

  • 一篇文章告诉你如何用Python控制Excel实现自动化办公

    目录 1.安装 2.操作一个简单的Excel文档 3. 操作简单Excel文档并添加数据格式 4.Excel中添加不同类型的数据 5.Excel中添加数据图表 最后:可能给予你助力的教程 总结 1.安装 2.操作一个简单的Excel文档 操作注释及代码: 操作完成后,数据存储结果如下: 3. 操作简单Excel文档并添加数据格式 操作代码如下: 附带数据格式的定义 操作效果如图所示: 4.Excel中添加不同类型的数据 操作代码如下: 将不同的数据按照指定的格式添加到文件中 代码执行结果如下:

  • 一篇文章教你如何排查.NET内存泄漏

    目录 前言 检查托管内存使用 生成dump文件 分析 core dump 总结 前言 内存泄漏通常表示:一个应用程序的某些对象在完成它的的生命周期后,由于它被其他对象意外引用,导致后续gc无法对它进行回收,长此以往就会导致程序性能的下降以及潜在的 OutOfMemoryException. 这篇我们通过一个内存泄漏工具对 .NET Core 程序进行内存泄漏分析,如果程序是跑在windows上,那直接可以使用 Visual Studio 进行诊断. 检查托管内存使用 在开始分析内存泄漏之前,你一

随机推荐