题目：

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; }
                
               
              
             
            
           
          
         
        
       
      
     

后面看别人的解答，事实上全然没有必要在队列中反序  仅仅要在存每一层输出结果的ArrayList中反序存入就能够了  以下是这样的思路的代码：

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; }}
            
           
          
         
        
       
      
     

看代码的长度就知道我之前的有多复杂了