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