二叉树攻略之：二叉树的锯齿形层序遍历

二叉树攻略之：二叉树的锯齿形层序遍历

题目

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如： 给定二叉树 [3,9,20,null,null,15,7],

/ \ 15 7

返回锯齿形层序遍历如下：

[ [3], [20,9], [15,7]]

解题思路

根据题意可知，此题是二叉树层序遍历的变种，我们可以用广度优先搜索的方式，对树进行层序遍历，用队列维护当前层的所有元素，当队列不为空的时候，求得当前队列的长度 size，每次从队列中取出 size 个元素进行拓展，然后进行下一次迭代。最后按奇偶来决定每一层的输出顺序

代码实现

public List> zigzagLevelOrder(TreeNode root) { Queue queue = new LinkedList<>(); List> res = new ArrayList<>(); if (root != null) { queue.offer(root); } List list ; while (!queue.isEmpty()) { int size = queue.size(); //当前层，元素的数量 list = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); //按顺序弹出队列元素，加入集合 list.add(node.val); if (node.left != null) { queue.offer(node.left); //当前元素的左子树入队，即把下一层的元素加入队列 } if (node.right != null) { queue.offer(node.right); //当前元素的右子树入队，即把下一层的元素加入队列 } } if (res.size() % 2 == 1) { //本题中奇数层要翻转下 Collections.reverse(list); } res.add(list); } return res;

最后

复杂度分析

时间复杂度：O(N)，其中 N 为二叉树的节点数。每个节点会且仅会被遍历一次。

空间复杂度：O(N)。我们需要维护存储节点的队列和存储节点值的队列，空间复杂度为 O(N)。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。