手撸二叉树之二叉树的锯齿形层序遍历
Hello, 大家好,今天是我参加 9 月更文的第 14 天,今天给大家带来的关于二叉树相关的算法题是从中序与后序遍历序列构造二叉树,正文如下:
题目
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:给定二叉树 [3,9,20,null,null,15,7],
复制代码
返回锯齿形层序遍历如下:
复制代码
解题思路
根据题意可知,此题是二叉树层序遍历的变种,我们可以用广度优先搜索的方式,对树进行层序遍历,用队列维护当前层的所有元素,当队列不为空的时候,求得当前队列的长度 size,每次从队列中取出 size 个元素进行拓展,然后进行下一次迭代。最后按奇偶来决定每一层的输出顺序.
代码实现
复制代码
最后
复杂度分析
时间复杂度:O(N),其中 N 为二叉树的节点数。每个节点会且仅会被遍历一次。
空间复杂度:O(N)。我们需要维护存储节点的队列和存储节点值的队列,空间复杂度为 O(N)。
版权声明: 本文为 InfoQ 作者【HelloWorld杰少】的原创文章。
原文链接:【http://xie.infoq.cn/article/896f4b077e9db429d4b4fb017】。文章转载请联系作者。
评论