专栏首页五分钟学算法图解LeetCode第 103 号问题:二叉树的锯齿形层次遍历

图解LeetCode第 103 号问题:二叉树的锯齿形层次遍历

该文已加入开源项目:LeetCodeAnimation(用动画的形式呈现解LeetCode题目的思路,目前 5000 Star )。地址:https://github.com/MisterBooo/LeetCodeAnimation

LeetCode上第103 号问题:二叉树的锯齿形层次遍历

题目描述

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 例如: 给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果: [ [3], [20,9], [15,7] ]

思路解析

该问题需要用到队列,与之前的二叉树的层次遍历类似,不同点在于在偶数层需要翻转一下。

  • 建立一个queue
  • 先把根节点放进去,这时候找根节点的左右两个子节点
  • 去掉根节点,此时queue里的元素就是下一层的所有节点
  • 循环遍历,将结果存到一个一维向量里
  • 遍历完之后再把这个一维向量存到二维向量里
  • 如果该层为偶数层,则reverse翻转一下
  • 以此类推,可以完成层序遍历

动画演示

动画演示GIF加载有点慢,请稍等片刻^_^

参考代码

 1class Solution{
 2public:
 3    vector<vector<int>> zigzagLevelOrder(TreeNode* root){
 4        vector<vector<int>> res2D;
 5        if (!root) return res2D;
 6        queue<TreeNode*> q;
 7        q.push(root);
 8        int level=1;
 9        int count=1;
10        int countTmp=0;
11        while(!q.empty()){
12                countTmp=0;
13                vector<int> res1D;
14                while (count>0){
15                    res1D.push_back(q.front()->val);
16                    if (q.front()->left) {q.push(q.front()->left);countTmp++;}
17                    if (q.front()->right) {q.push(q.front()->right);countTmp++;}
18                    q.pop();
19                    count--;
20                }
21                if (level%2==0) reverse(res1D.begin(),res1D.end());   
22                count=countTmp;
23                res2D.push_back(res1D);
24                level++;               
25        }
26        return res2D;
27    }
28};

代码截图

本文分享自微信公众号 - 五分钟学算法(blgczzz)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-20

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每天一算: Number of Boomerangs

    五分钟学算法
  • 一道简单的数组遍历题,加上四个条件后感觉无从下手

    给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个...

    五分钟学算法
  • 每天一算:Sort Colors

    结合三路快排partition思路的应用,设定两个索引,一个从左往右滑动zero,一个从右往左滑动two,遍历nums,当nums[i]的值为1时,i++;当n...

    五分钟学算法
  • 保存一下dedecms数据库表和字段说明,方便日后查询

    玩dedecms有一段时间,对它的字段不是很了解,在此做个记录,方便日后查询 dede数据库字段说明: dede_addonarticle 附加文章...

    ytkah
  • 有些话想和Java程序员说!

    很多大厂都喜欢招看过源码的程序员,很多面试过程中都会深入的问一些源码级别的问题,比如Spring、Dubbo等等这些。

    帅地
  • 解决python 缺少 'python.

    greenlet.h:8:20: 致命错误: Python.h:没有那个文件或目录

    py3study
  • 设计模式--代理模式(附源码分析)

     在平时的开发过程中,我们实现方法的调用往往只是普通的对象调用方法,实现复杂的业务就是一层一层的对象调用方法依次进行实现,但是如果我要实现在某些方法执行前或者...

    小勇DW3
  • 剖析Java中HashMap数据结构的源码及其性能优化

    存储结构 首先,HashMap是基于哈希表存储的。它内部有一个数组,当元素要存储的时候,先计算其key的哈希值,根据哈希值找到元素在数组中对应的下标。如果这个位...

    凯哥Java
  • Java基础19(01)总结IO流,异常try…catch,throws,File类

    1:异常(理解) (1)程序出现的不正常的情况。 (2)异常的体系 Throwable |--Error 严重问题,我们不处理。 |--Excepti...

    奋斗蒙
  • 三周学会小程序第三讲:服务端搭建和免费部署

    通过第二讲我们已经知道了怎么快速搭建一个小程序客户端,当然服务端也是必不可少的。登录验证,内容存储等等都离不开服务端。

    用户1093975

扫码关注云+社区

领取腾讯云代金券