题解 | #按之字形顺序打印二叉树#

按之字形顺序打印二叉树

http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

描述

给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替)
例如:
给定的二叉树是{1,2,3,#,#,4,5}

示例1

输入:
{1,2,3,#,#,4,5}

返回值:
[[1],[3,2],[4,5]]

示例2

输入:
{8,6,10,5,7,9,11}

返回值:
[[8],[10,6],[5,7,9,11]]

示例3

输入:
{1,2,3,4,5}

返回值:
[[1],[3,2],[4,5]]

思路

按层遍历二叉树,不知道大家了不了解,按层便利就是将每层的元素,按照从左到右的顺序输出。而这道题要求的 之 字形便利,则是第一层是从左到右,下一层则是从右到左。如果之前会写按层遍历,在写这道题会相对简单一点。

以上面这棵树为例:

  1. 首先咱们通过 队列 这个数据结构来实现每层元素的存储,当遍历到第一层的时候,这时是从左到右的顺序入队列,入了队列之后值存入到集合中。然后再将左节点以及右节点入队。
  2. 这时到了第二层,这层的顺序是从右到左了,从队列中出队,弹出元素,将上一层所有的元素都弹出后,以相反的顺序存入到集合中。
  3. 之后重复上面的动作,知道完成便利。

AC代码

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) {
            return result;
        }
        // 创建一个队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点先入队
        queue.offer(pRoot);
        // 当队列不为空时
        while (!queue.isEmpty()) {

            int size = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            // 仅遍历当前层的元素,因为结果是按照层的维度存储的
            for (int i = 0; i < size; i ++) {
                // 弹出元素
                TreeNode node = queue.poll();
                list.add(node.val);
                // 如果左节点不为空,则入队
                if (node.left != null) {
                    queue.offer(node.left);
                }
                // 如果右节点不为空,则入队
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 判断一下是否为奇数层,如果是,则将结果反着存储,
            // 这里将根节点那层设定为 第 0 层,为偶数层
            if (result.size() % 2 == 1) {
                Collections.reverse(list);
            }
            // 将结果以 层 为维度存储
            result.add(list);
        }
        return result;
    }

时间复杂度:O(N), N 为节点数,每个节点都要遍历一次
空间复杂度:o(N), N 为节点数,将这些节点存入到队列中

最后

做这道题之前最后先做一下 层序遍历二叉树,这道题只不过是变了一下而已。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索:【蘑菇睡不着】交个朋友~
也可以扫描下方二维码。

图片说明

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
01-23 09:08
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议