专栏首页desperate633LintCode 二叉树的锯齿形层次遍历题目分析代码

LintCode 二叉树的锯齿形层次遍历题目分析代码

题目

给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行)

Paste_Image.png

分析

较为简单,直接在层次遍历的基础上改,将偶数行反转即可,可以加一个boolean变量判断,也可以最后直接在res上反转

代码

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
 
 
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: A list of lists of integer include 
     *          the zigzag level order traversal of its nodes' values 
     */
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null)
            return new ArrayList<>();
        
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        
        Queue<TreeNode> list = new LinkedList<>();
        
        list.offer(root);
        boolean normalorder = true;
        
        while(!list.isEmpty()) {
            int size = list.size();
            
            ArrayList<Integer> level = new ArrayList<>();
            for(int i=0;i<size;i++) {
                TreeNode cur = list.poll();
                level.add(cur.val);
                if(cur.left != null)
                    list.offer(cur.left);
                if(cur.right != null)
                    list.offer(cur.right);
            }
            
            if(normalorder)
                res.add(level);
            else {
                Collections.reverse(level);
                res.add(level);
            }
            normalorder = !normalorder;
        }
        //Collections.reverse(res);
        
        
        return res;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode 二叉树的层次遍历 II题目代码

    给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)

    desperate633
  • LintCode 二进制求和题目分析代码

    desperate633
  • [编程题] 奇怪的表达式求值代码

    常规的表达式求值,我们都会根据计算的优先级来计算。比如*/的优先级就高于+-。但是小易所生活的世界的表达式规则很简单,从左往右依次计算即可,而且小易所在的世界没...

    desperate633
  • Qt编写地图综合应用17-地址经纬度互转

    地址和经纬度互相转换的功能也经常用到,比如上次的路线方案查询的功能,之前官网是提供了直接输入出发地点和目的地的中文汉字,就可以查询到最优的路线,后面只支持输入出...

    feiyangqingyun
  • 【IOT迷你赛】基于LBS的物联网智能家居

    很庆幸成为腾讯云TencentOS嵌入式操作系统的试用者,能够尝鲜使用腾讯云“嵌入式操作系统+IOT开发板+腾讯云IOT服务”的全套开发套件。本...

    用户3215831
  • matlab演奏《雨碎江南》

    先请大家听一下上面这首曲子,演奏的是著名的古风乐曲《雨碎江南》。你是否已经融入了那一场夜雨,感受到了雨水的清凉。大家一定想问:用的是什么乐器?

    matlab爱好者
  • python:使用beautifulSoup抓网页

    超级大猪
  • Python-数据解析-职位信息-中

    在 Spider 类中,定义一个用于解析网页的方法 parse_page(),分别使用 re 模块、lxml 和 bs4 库进行实现。

    小团子
  • 浅探JavaScript深拷贝和浅拷贝

    对象和数组的拷贝对我来说一直都是一个比较模糊的概念,一直有点一知半解,但是在实际工作中又偶尔会涉及到,有时候还会一不小心掉坑里,不知道大家有没有同样的感受,因此...

    Fundebug
  • XSS手工利用方式-FreeBuf.COM

    0×00 vps 当我们在插入的xss,在客户端成功执行了相关的操作后,需要将获取的内容传递出来,可以选择购买VPS或者免费的dnslog平台通过ge...

    奶糖味的代言

扫码关注云+社区

领取腾讯云代金券