LeetCode(Trees&Graphs)Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal

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   7

return its zigzag level order traversal as:

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

思路：其实就是依据奇偶层反序输出二叉树的层序遍历结果。写一个二叉树的层序遍历，控制奇偶层反转顺序即可。代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        ArrayList<TreeNode> nodeQueue=new ArrayList<>();
        
        if(root==null){
            return res;
        }
        nodeQueue.add(root);
        int  k=0;
        while(!nodeQueue.isEmpty()){
            k++;
            int len=nodeQueue.size();
            List<Integer> list=new ArrayList<Integer>();
            
            for(int i=0;i<len;i++){
                 TreeNode temp=nodeQueue.remove(0);
                 list.add(temp.val);
                 if(temp.left!=null){
                        nodeQueue.add(temp.left);
                 }
                 if(temp.right!=null){
                        nodeQueue.add(temp.right);
                 }
            }
            if(k%2==0){
                Collections.reverse(list);
            }
            res.add(list);
        }
        return res;
    }
}