把二叉树打印成多行

标签: 剑指offer  二叉树打印成多行

题目

从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

思路1

层序遍历,只有一点需要考虑,就是如何把层序遍历序列按层分开来,因为返回的是每一层的遍历序列。

最简单的做法是遍历当前层的时候就逐步确定下一层最右边的结点(遍历的过程中,下一层的最右结点一直在更新),这样当这一层遍历完时,下一层的最右结点也就确定了,这样当遍历下一层的时候就有了一个终点,这样子就完成了分层。

    /**
     * 解法1:记录每层的最右节点:
     *      遍历当前层的时候就逐步确定下一层最右边的结点(遍历的过程中,下一层的最右结点一直在更新),
     *      这样当这一层遍历完时,下一层的最右结点也就确定了,这样当遍历下一层的时候就有了一个终点,
     *      这样子就完成了分层。
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        ArrayList<Integer> arr = new ArrayList<>();
        if (root == null)
            return result;
        TreeNode pre = root,  now = null ;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            arr.add(node.val);
            if (node.left != null) {
                q.offer(node.left);
                now = node.left;
            }
            if (node.right != null) {
                q.add(node.right);
                now = node.right;
            }
            //当前遍历节点是某层的最右节点时就添加arr到result中,并清空arr以便接着存下一层
            if (pre == node) {
                result.add(arr);
                /*
                 * 这里直接用clear错误,因为这里arr指向的这个ArrayList<Integer>对象现在保存在result中,
                 * arr.clear()意味着把这个对象里的内容清空了,所以result里的对象就为空了!
                 * 应该将arr再重新指向一个新的ArrayList对象即可!
                 */
                //arr.clear();
                arr = new ArrayList<>();
                //pre更新为下一层节点的最右节点,即为node.right如果node.rigth存在的话!
                pre = now;
            }
        }
        return result;
    }

思路2

使用一个队列,根据队列中元素的个数来确定分层,当队列中的某一层元素全部遍历完(遍历完就会弹出队列)后,队列中就只有下一层的元素,所以,可以依据这个来分层。

    /**
     * 解法2:使用一个队列
     *      根据队列中元素的个数来确定分层,当队列中的某一层元素全部遍历完(遍历完就会弹出队列)后,
     *      队列中就只有下一层的元素此时队列长度length就是下一层元素个数,然后再遍历这一层(即遍历length长度)时将下一层入队。
     */
    public List<List<Integer>> levelOrder3(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        //只用一个队列来做
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            List<Integer>  oneLevel = new ArrayList<>();
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                //获取队头元素而不移出该元素,使用element()或者peek(),获取并移出使用poll()
                TreeNode node = q.poll();
                oneLevel.add(node.val);
                if (node.left!=null) q.offer(node.left);
                if (node.right!=null) q.offer(node.right);
            }
            result.add(oneLevel);
        }
        return result;
    }

思路3

思路2需要在队列中确定某一层的个数,这个操作可以用两个队列来实现,也就是遍历一个队列的所有孩子放到另一个队列中;遍历另一个队列时,又把另一个队列中的所有孩子又放回来这个队列,这样也实现了分层。而且,两个队列始终有一个队列保持为空。这样子的操作叫滚动队列。

    /**
     * 解法3:使用两个队列current和next
     *      只用一个队列要每次记录下一层的个数,这个操作其实可以用两个队列来实现,也就是遍历一个队列的所有孩子放到另一个队列中;
     *      遍历另一个队列时,又把另一个队列中的所有孩子又放回来这个队列,这样也实现了分层。
     *      而且,两个队列始终有一个队列保持为空。这样子的操作叫滚动队列。
     */
    public List<List<Integer>> levelOrder4(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        //使用两个队列来做
        Queue<TreeNode> current = new LinkedList<>();
        Queue<TreeNode> next = new LinkedList<>();

        if(root == null) {
            return result;
        } else {
            current.offer(root);
        } 

        while (!current.isEmpty()) {
            //保存某一层的元素
            ArrayList<Integer> level = new ArrayList<>();
            while (!current.isEmpty()) {
                TreeNode node = current.poll();
                level.add(node.val);
                if (node.left != null) next.add(node.left);
                if (node.right != null) next.add(node.right);
            } 
            result.add(level);
            // 交换两个队列
            Queue<TreeNode> tmp = current;
            current = next;
            next = tmp;
        } 
        return result;
    }

思路4

虽然是层序遍历,但是我们也可以用DFS来做,虽然DFS是深度优先(这是从竖直方向看),但是从水平方向看,每一层遍历结点的顺序依然是从左到右。这就是用DFS做的依据。

    /**
     * 解法4:递归法
     *      虽然是层序遍历,但是我们也可以用dfs来做,虽然dfs是深度优先(这是从竖直方向看),
     *      但是从水平方向看,每一层遍历结点的顺序依然是从左到右。这就是用dfs做的依据。
     */
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        //根节点为第一层
        traverse(root, 1, result);
        return result;
    } 

当然这题我们还需要将给定的数组转化成二叉树,使用下面的函数实现:

    /**
     * 根据给定的数组创建二叉树 
     */
    public TreeNode createBinaryTreeByArray(int[] array, int index) {
        TreeNode tn = null;
        if (index < array.length) {
            int value = array[index];
            tn = new TreeNode(value);
            tn.left = createBinaryTreeByArray(array, 2 * index + 1);
            tn.right = createBinaryTreeByArray(array, 2 * index + 2);
            return tn;
        }
        return tn;
    }

最终的测试代码如下:

    @Test
    public void test1() {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the length of Array:");
        while(sc.hasNext()) {   
            int length = sc.nextInt();
            int[] arr = new int[length];
            for(int i = 0;i<length;i++) {
                arr[i] = sc.nextInt();
            }
            TreeNode root = createBinaryTreeByArray(arr, 0);
            System.out.println(levelOrder1(root));
            System.out.println(levelOrder2(root));
            System.out.println(levelOrder3(root));
            System.out.println(levelOrder4(root));
        }
        sc.close();
    }
}

测试结果如下:
这里写图片描述

版权声明:本文为DjokerMax原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/DjokerMax/article/details/82744229

智能推荐

【Spark 内核】 Spark 内核解析-下

Spark内核泛指Spark的核心运行机制,包括Spark核心组件的运行机制、Spark任务调度机制、Spark内存管理机制、Spark核心功能的运行原理等,熟练掌握Spark内核原理,能够帮助我们更好地完成Spark代码设计,并能够帮助我们准确锁定项目运行过程中出现的问题的症结所在。 Spark Shuffle 解析 Shuffle 的核心要点 ShuffleMapStage与ResultSta...

Reflect反射的基础知识

写个父类: 写个子类: 利用反射获得该子类中的属性,方法,构造,父类及接口: 运行结果:...

spring cloud netflix (07) 服务的消费者(feign)

前言 完整知识点:spring cloud netflix 系列技术栈 Feign (同步通信 HTTP通信) feign是基于接口完成服务与服务之间的通信的 搭建Feign服务 项目结构 项目搭建 pom.xml application类 application.yml 使用feign完成服务与服务之间的通信 feign是基于接口完成服务与服务之间的通信的...

AtCoder Beginner Contest 174 E.Logs

AtCoder Beginner Contest 174 E.Logs 题目链接 到最后才发现是二分,菜菜的我/(ㄒoㄒ)/~~ 我们直接二分 [1,max{a[i]}][1,max\lbrace a[i]\rbrace][1,max{a[i]}] 即可,对每一个 midmidmid,每个数 a[i]a[i]a[i] 只需要切 a[i]−1mid\frac{a[i]-1}{mid}mi...

小程序基础与实战案例

小程序开发工具与基础 小程序开发准备: 申请小程序账号( appid ) 下载并安装微信开发者工具 具体步骤如下: 先进入 微信公众平台 ,下拉页面,把鼠标悬浮在小程序图标上 然后点击 小程序开发文档 照着里面给的步骤,就可以申请到小程序账号了。 然后就可以下载 开发者工具 了 下载完打开后的界面就是这个样子 下面让我们来新建一个小程序开发项目: 在AppID输入自己刚刚注册的AppID就可以,或...

猜你喜欢

VMware centOS7 下通过minikube部署Kubernetes

1、环境准备: VMware CentOS-7-x86_64 CPU:2*2core 内存:8G 宿主机和虚拟机需网络互通,虚拟机外网访问正常 Centos发行版版本查看:cat /etc/centos-release root用户操作 2、禁用swap分区 Kubernetes 1.8开始要求关闭系统的Swap,可暂时关闭或永久禁用, 使用 $ free -m 确认swap是否为开启状态 $ s...

逻辑回归与scikit-learn

欢迎关注本人的微信公众号AI_Engine LogisticRegression 算法原理 一句话概括:逻辑回归假设数据服从伯努利分布,通过极大化似然函数(损失函数)的方法,运用梯度下降或其他优化算法来求解参数,来达到将数据二分类的目的。 定义:逻辑回归(Logistic Regression)是一种用于解决二分类(0 or 1)问题的机器学习方法,用于估计某种事物的可能性(不是概率)。比如某用户...

指针OR数组?用他们来表达字符串又有何不同?

cocowy的编程之旅 在学习C语言的过程中我们经常可以看到或者听到这样一句话:数组其实等价于指针,例如: 在这里可以轻松的看出输出后他们的值相等,其实在计算机内存里面,p为本地变量,有着他自己的作用域。而指针变量q保存着这个数组的首地址,通过*号指向这个地址保存的变量值。 然而我们再看一个例子: 这个时候计算机报错,这是为什么呢? 其实原因很简单,指针说指向的这个字符串的地址是位于计算机代码段地...

广度搜索

广度搜索的基本使用方法 广度搜索不同于深度搜索,是一种一步一步进行的过程,每一个点只记录一遍。需要用到队列记录每一步可以走到的位置,找到目标位置输出步数即可。 用到的知识:结构体、队列 如图 首先我们需要定义一个结构体来存储每个遍历到的点和步数 广搜不会用到递归,所以可以直接在主函数里写,这里需要定义一个结构体队列 初始化队列并将起始点入列 遍历 完整代码...

NIO Socket 编程实现tcp通信入门(二)

1、NIO简介 NIO面向通道和缓冲区进行工作,数据总是从通道读取到缓冲区中,或者从缓冲区写入到通道中。可以双向传输数据,是同步非阻塞式IO。NIO还引入了选择器机制,从而实现了一个选择器监听多个底层通道,减少了线程并发数。用NIO实现socket的Tcp通信需要掌握下面三个知识点: Buffer 缓冲区 Channel 通道 Selector 选择器   2、java.nio.Buff...