今天小编给大家分享一下C++怎么实现二叉树的字形层序遍历的相关知识点，内容详细，逻辑 香港云主机清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。For example:
Given binary tree[3,9,20,null,null,15,7], 3
/
9 20
/
15 7return its zigzag level order traversal as:[
[3],
[20,9],
[15,7]
]这道二叉树的之字形层序遍历是之前那道Binary Tree Level Order Traversal的变形，不同之处在于一行是从左到右遍历，下一行是从右往左遍历，交叉往返的之字形的层序遍历。最简单直接的方法就是利用层序遍历，并使用一个变量 cnt 来统计当前的层数（从0开始），将所有的奇数层的结点值进行翻转一下即可，参见代码如下：解法一：我们可以将上面的解法进行优化一下，翻转数组虽然可行，但是比较耗时，假如能够直接计算出每个结点值在数组中的坐标，就可以直接进行更新了。由于每层的结点数是知道的，就是队列的元素个数，所以可以直接初始化数组的大小。此时使用一个变量 leftToRight 来标记顺序，初始时是 true，当此变量为 true 的时候，每次加入数组的位置就是i本身，若变量为 false 了，则加入到 size-1-i 位置上，这样就直接相当于翻转了数组。每层遍历完了之后，需要翻转leftToRight 变量，同时不要忘了将 oneLevel 加入结果 res，参见代码如下：解法二：我们也可以使用递归的方法来解，这里实际上用的是先序遍历，递归函数需要一个变量 level 来记录当前的深度，由于 level 是从0开始的，假如结果 res 的大小等于 level，就需要在结果 res 中新加一个空集，这样可以保证 res[level] 不会越界。取出 res[level] 之后，判断 levle 的奇偶，若其为偶数，则将 node->val 加入 oneLevel 的末尾，若为奇数，则加在 oneLevel 的开头。然后分别对 node 的左右子结点调用递归函数，此时要传入 level+1 即可，参见代码如下：解法三：以上就是“C++怎么实现二叉树的字形层序遍历”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注开发云行业资讯频道。
这篇文章主要介绍“php常量和变量有什么不同”，在日常操作中，相信很多人在php常量和变量有什么不同问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”php常量和变量有什么不同”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！1、常…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
