题目：

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]]

链接： 

题解：

跟level order traversal一样，只不过多了一个flag来判断添加元素的顺序。

Time Complexity - O(n)， Space Complexity - O(n).

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public List
     
      
       > zigzagLevelOrder(TreeNode root) {        List
       
        
         > res = new ArrayList<>();        if(root == null)            return res;        ArrayList
         
           list = new ArrayList<>();        Queue
          
            q = new LinkedList<>(); q.offer(root); int curLevel = 1, nextLevel = 0; boolean zigZagFlag = true; while(!q.isEmpty()) { TreeNode node = q.poll(); if(zigZagFlag) list.add(node.val); else list.add(0, node.val); curLevel--; if(node.left != null) { q.offer(node.left); nextLevel++; } if(node.right != null) { q.offer(node.right); nextLevel++; } if(curLevel == 0) { curLevel = nextLevel; nextLevel = 0; res.add(new ArrayList
           
            (list)); list.clear(); zigZagFlag = !zigZagFlag; } } return res; }}
           
          
         
        
       
      
     

 

二刷:

注意要写得流畅。   有一个boolean变量 zigzag来确定合适按照正序 / 逆序 添加结果到每一个level的list里。

Java:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public List
     
      
       > zigzagLevelOrder(TreeNode root) {        List
       
        
         > res = new ArrayList<>();        if (root == null) return res;        List
         
           list = new ArrayList<>();        Queue
          
            q = new LinkedList<>(); q.offer(root); int curLevel = 1, nextLevel = 0; boolean zigzag = true; while (!q.isEmpty()) { TreeNode node = q.poll(); if (zigzag) list.add(node.val); else list.add(0, node.val); curLevel--; if (node.left != null) { q.offer(node.left); nextLevel++; } if (node.right != null) { q.offer(node.right); nextLevel++; } if (curLevel == 0) { curLevel = nextLevel; nextLevel = 0; res.add(new ArrayList<>(list)); list.clear(); zigzag = !zigzag; } } return res; }}
          
         
        
       
      
     

 

测试：