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,null,null,15,7],    3   / \  9  20    /  \   15   7return its zigzag level order traversal as:[  [3],  [20,9],  [15,7]]

难度：medium

题目：给定二叉树，返回其之字型层次遍历结点值。

思路：层次遍历

Runtime: 1 ms, faster than 90.32% of Java online submissions for Binary Tree Zigzag Level Order Traversal.

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public List
    
     
      > zigzagLevelOrder(TreeNode root) {        List
      
       
        > result = new ArrayList<>();        if (null == root) {            return result;        }        Queue
        
          queue = new LinkedList<>();        queue.add(root);        int currentLevelCount = 1, nextLevelCount = 0;        boolean direction = true;        while (!queue.isEmpty()) {            List
         
           curLevelElems = new ArrayList<>(currentLevelCount); for (int i = 0; i < currentLevelCount; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.add(node.left); nextLevelCount++; } if (node.right != null) { queue.add(node.right); nextLevelCount++; } if (direction) { curLevelElems.add(node.val); } else { curLevelElems.add(0, node.val); } } result.add(curLevelElems); currentLevelCount = nextLevelCount; nextLevelCount = 0; direction = !direction; } return result; }}