题目：

?

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / 
  9  20
    /  
   15   7

?

return its zigzag level order traversal as:

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

解题：

这题其实和二叉树的层序遍历很类似 仅仅是在这个基础上加上一个左右方向 一开始我的思维被局限住了 写了一个很冗余的代码版本 实现思路是这样的 当需要从右到左输出的时候 我把队列里面的节点输出然后 反序存回队列

代码：

?

public static List
  
   > zigzagLevelOrder(TreeNode root) {
		
		List
   
    > result=new ArrayList
    
     >();//存放最终结果 boolean isLeftToRight=false;//从左到右的方向 Queue
     
       nodeQueue=new LinkedList<>();//存放节点 便于每一层遍历 //处理根节点 if(root==null) return result; else { List
      
        list=new ArrayList<>(); list.add(root.val); result.add(list); nodeQueue.offer(root); } while(!nodeQueue.isEmpty()) { int size=nodeQueue.size(); List
       
         tempResult=new ArrayList<>();//用来暂时存放每一层节点的遍历结果 Stack
        
          stack=new Stack<>();//用来辅助将队列倒序 if(isLeftToRight) { //将队列里面的节点都先出队列进栈再出栈进队列 使得和原来的顺序刚好相反 for(int i=0;i
         
          0)//从左到右 { size--; TreeNode tempNode=nodeQueue.poll(); if(tempNode.left!=null) { nodeQueue.offer(tempNode.left); tempResult.add(tempNode.left.val); } if(tempNode.right!=null) { nodeQueue.offer(tempNode.right); tempResult.add(tempNode.right.val); } } if(!tempResult.isEmpty()) result.add(tempResult); //循环退出 表示一层已经遍历完了 这时候重置方向标志位 isLeftToRight=false; } else { //将队列里面的节点都先出队列进栈再出栈进队列 使得和原来的顺序刚好相反 for(int i=0;i
          
           0)//从右到左 { size--; TreeNode tempNode=nodeQueue.poll(); if(tempNode.right!=null) { nodeQueue.offer(tempNode.right); tempResult.add(tempNode.right.val); } if(tempNode.left!=null) { nodeQueue.offer(tempNode.left); tempResult.add(tempNode.left.val); } } if(!tempResult.isEmpty()) result.add(tempResult); //循环退出 表示一层已经遍历完了 这时候重置方向标志位 isLeftToRight=true; } } return result; }
          
         
        
       
      
     
    
   
  

?

?

public static List
  
   > zigzagLevelOrder2(TreeNode root) {
		
		List
   
    > result=new ArrayList
    
     >();//存放最终结果 Queue
     
       nodeQueue=new LinkedList<>();//存放节点 int flag=1;//flag为奇数的时候 从左到右 为偶数的时候从右到左； if(root==null) return result; else { nodeQueue.add(root); } while(!nodeQueue.isEmpty()) { int count=nodeQueue.size(); List
      
        tempResult=new ArrayList<>(); while(count>0) { TreeNode tempNode=nodeQueue.poll(); count--; if(flag%2!=0)//从左到右 { tempResult.add(tempNode.val); } else {// tempResult.add(0,tempNode.val); } if(tempNode.left!=null) nodeQueue.add(tempNode.left); if(tempNode.right!=null) nodeQueue.add(tempNode.right); } if(!tempResult.isEmpty()) result.add(tempResult); flag++; } return result; } } 
      
     
    
   
  

?