【算法打卡】二叉树的锯齿形层序遍历

vlambda
2021-01-05

【算法打卡】二叉树的锯齿形层序遍历

难度：中等

题目：

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

-------------------------------------------

这个需求的关键字是二叉树、锯齿、遍历

其实就是要求遍历一颗二叉树，只不过这不是随意的遍历，而是锯齿式地遍历，就是第一行从左到右遍历（当然第一行还有一个节点，左右都一样），然后第二行从右到左遍历，第三行又是反过来，从左到右遍历......

这个看下去就跟树的广度优先遍历很像，只不过这个是左右遍历的顺序会随着层级的不同而有规律地来回发生变化。

广度优先，学名广度优先搜索法，英文名Breadth First Search，缩写BFS，玩过爬虫的童鞋应该不会陌生。他是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。

用在二叉树遍历，简单来说就是一层一层地遍历。

思路：

先用一个容器把每一层的节点存起来，用作后面的遍历。
遍历后，把原来层级数据踢出，把该层的每个节点的子节点按从左到右放进容器，如此反复。
遍历方面，判断从左往右还是从右往左遍历可以根据层级判定，单数左到右（插入到数组开头），双数右到左（插入到数组末尾）（这里插入用LinkedList代替普通list，快速插入，两边插入都是O(1)）。

代码：

public List<List<Integer>> zigzagLevelOrder2(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { // 该层的节点数量 int count = queue.size(); LinkedList<Integer> sub = new LinkedList<>();
 while (count > 0) { TreeNode node = queue.poll(); // 根据层次来判断用哪种顺序 if (result.size() % 2 == 0) sub.add(node.val); else sub.add(0, node.val);
 if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); count--; } result.add(sub); } return result;}