题目
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）
示例
给定二叉树 [3,9,20,null,null,15,7]
返回：
[
[3],
[20,9],
[15,7]
]
分析
z字型遍历，是二叉树层次遍历的增强版。
普通层次遍历，可以使用队列实现；
z遍历，需要记录当前层，根据当前层的奇偶行来调整队列的进出方向；
普通层次遍历
public List<Integer> levelQuery(TreeNode root,List<Integer> list){
TreeNode node = root;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(node);
while(queue.size()>0){
node = queue.poll();
list.add(node.val);
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
return list;
}
记录当前层的层次遍历
TreeNode node = root;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(node);
int deep = 1;
while(queue.size()>0){
int size = queue.size();
for (int i = 0; i < size; i++) {
node = queue.poll();
list.add(node.val);
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
System.out.println(deep);
deep++;
}
return list;
解答
双端队列
/**
* 树：前序int[] pre = {1,2,4,5,3,6}; 中序int[] mid = {4,2,5,1,3,6};
*
* 第一种实现：
* deep=1 deq={1}
* 1 ->poll
* l r offer
* 2 3
*
* deep=2 deq={2 3}
* 3 ->pollLast
* r l push
* 6 2
* 2 ->pollLast
* r l push
* 4 5 6
*
* deep=3 deq={4 5 6}
* 4 ->poll
* 5 ->poll
* 6 ->poll
*
* 第二种实现：
* deep=1 deq={1}
* 1 ->pollLast
* l r push
* 3 2
*
* deep=2 deq={3 2}
* 3 ->poll
* r l offer
* 2 6
* 2 ->poll
* r l offer
* 6 5 4
*
* deep=3 deq={6 5 4}
* 4 ->pollLast
* 5 ->pollLast
* 6 ->pollLast
*
*
* 以下方法采用第二种实现方法
* @param root
* @return
*/
private List<List<Integer>> zserachByDeque(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
deque.add(root);
int deep = 1;
while(deque.size() > 0){
int size = deque.size();
List<Integer> curDeepList = new ArrayList<>();
for (int i = 0; i < size; i++) {
//奇数层，尾出头进
if(deep%2 == 1){
TreeNode node = deque.pollLast();
if(node.left!=null){
deque.push(node.left);
}
if(node.right!=null){
deque.push(node.right);
}
curDeepList.add(node.val);
}else{
//偶数层，尾进头出
TreeNode node = deque.poll();
if(node.right!=null){
deque.offer(node.right);
}
if(node.left!=null){
deque.offer(node.left);
}
curDeepList.add(node.val);
}
}
deep++;
result.add(curDeepList);
}
return result;
}
stack + queue
/**
* stack + queue
*
* deep=1
* 1 -> pop
* queue 1
* 1 -> l r push
* stack={2 3} result={1}
*
* deep=2
* 3 -> pop
* 2 -> pop
* queue 3 2
*
* 3-> r l push
* stack={6} result={1 3}
*
* 2-> r l push
* stack={6 5 4} result={1 3 2}
*
* deep=3
* 6 -> pop
* 5 -> pop
* 4 -> pop
* ...
*
*
* @param root
* @return
*/
private List<List<Integer>> zserach2(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
int deep = 1;
while(stack.size()>0){
int size = stack.size();
//临时变量和队列
List<Integer> curDeepList = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
for (int i = 0; i < size; i++) {
queue.add(stack.pop());
}
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
curDeepList.add(node.val);
if(deep % 2 == 1){
if(node.left!=null){
stack.push(node.left);
}
if(node.right!=null){
stack.push(node.right);
}
}else{
if(node.right!=null){
stack.push(node.right);
}
if(node.left!=null){
stack.push(node.left);
}
}
}
deep++;
result.add(curDeepList);
}
return result;
}
