leetcode刷题记录 103 二叉树的锯齿形层次遍历
leetcode 103 二叉树的锯齿形层次遍历
看到这道题,层次遍历的一般思路是使用队列来存放每一层的结点,然后逐一出队列存放在结果集中。但这道题还需要我们进行锯齿形的遍历,即先从左到右,再从右到左进行下层遍历,交替进行。
于是我观察案例,以根结点所在层为0开始,凡是为偶数的,是从左往右遍历,奇数的是从右往左遍历。**所以设置一个level作为当前层,若是偶数层,则将结点通过尾插法放到结果队列后面;若是奇数层,则将结点通过头插法放到结果队列中。**为了实现头插和尾插,我选择LinkedList作为存放结果集的数据结构(因为LinkedList底层是双向链表)。于是代码如下: