查看: 1420|回复: 0

Lintcode71 Binary Tree Zigzag Level Order Traversal solution 题解

[复制链接]
认证徽章
论坛徽章:
0
发表于 2017-12-1 23:31 | 显示全部楼层 |阅读模式
【题目描述】

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行)
【题目链接】
www.lintcode.com/en/problem/binary-tree-zigzag-level-order-traversal/
【题目解析】
这道题目其实本质上还是一个按层遍历(或者说宽度优先搜索)的算法,我们不妨先不考虑“之”字形的限制,而是简单的按照一层一层、每层从左到右的顺序进行。
首先,我们可以简单的获取第一层:[root],按照数学归纳法的思想,如果我们可以通过第K层求出第K+1层的话,就意味着我们可以求出任意一层。
而这个过程也是简单的,如果第K层是[node1, node2, node3 ... nodek]的话,那么第K+1层理想情况下就是[node1 -> left, node1 -> right, node2 -> left, node2 -> right, node3 -> left, node3 -> right ... nodek -> left, nodek -> right]。
但是实际上,由于有些节点不存在左右子节点,所以在对应位置上出现的是null,我们需要将这些null值去除掉,而在去除掉之后,我们就可以得到第K+1按照从左到右顺序的排列结果。
至此,我们的问题已经基本解决,那么如何处理之字形呢?这个很简单,按照层数的奇偶将所有偶数层的顺序反转即可~
【参考答案】
www.jiuzhang.com/solutions/binary-tree-zigzag-level-order-traversal/



作者:程风破浪会有时
链接:http://www.jianshu.com/p/f5c948e649e5
來源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会 限时8.5折

【架构革新 高效可控】2020年6月4日~6日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
TOP技术积分榜 社区积分榜 徽章 团队 统计 知识索引树 积分竞拍 文本模式 帮助
  ITPUB首页 | ITPUB论坛 | 数据库技术 | 企业信息化 | 开发技术 | 微软技术 | 软件工程与项目管理 | IBM技术园地 | 行业纵向讨论 | IT招聘 | IT文档
  ChinaUnix | ChinaUnix博客 | ChinaUnix论坛
CopyRight 1999-2011 itpub.net All Right Reserved. 北京盛拓优讯信息技术有限公司版权所有 联系我们 
京ICP备09055130号-4  北京市公安局海淀分局网监中心备案编号:11010802021510 广播电视节目制作经营许可证:编号(京)字第1149号
  
快速回复 返回顶部 返回列表