【LeetCode】103.二叉树的锯齿形层序遍历(之字形遍历)

1.问题

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

"图1"

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -100 <= Node.val <= 100

2.解题思路

从结果集来看，该题是【LeetCode】102.二叉树的层序遍历的结合，每层既有正序输出，又有逆序输出。只要给定一个标识，奇数层正序输出，而偶数层逆序输出即可解决。

3.代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //利用层序遍历，奇数层从左往右，偶数层从右往左
        if(null == root){
            return new ArrayList();
        }
        List<List<Integer>> res=new ArrayList();
        List<Integer> tempList=new ArrayList();
        List<TreeNode> temp=new ArrayList<TreeNode>();
        temp.add(root);
        temp.add(null);
        TreeNode node;
        int layer=1;
        while(!temp.isEmpty()){
            node=temp.remove(0);
            if(null != node){
                //奇数层从左往右，偶数层从右往左
                if(layer%2==0){
                    tempList.add(0, node.val);
                } else {
                    tempList.add(node.val);
                }
                if(null!=node.left){
                    temp.add(node.left);
                }
                if(null!=node.right){
                    temp.add(node.right);
                }
            } 
            //本层已遍历完毕
            else if(!tempList.isEmpty()){
                res.add(tempList);
                tempList=new ArrayList();
                temp.add(null);
                layer++;
            }
        }
        return res;
    }
}